1 /*************************************************************************  2     > File Name: 28_KLeastNumbers.cpp  3     > Author: Juntaran  4     > Mail: JuntaranMail@gmail.com  5     > Created Time: 2016年08月31日 星期三 19时45分41秒  6  ************************************************************************/  7   8 #include <stdio.h>  9 #include <bits/stdc++.h> 10  11 using namespace std; 12  13  14 // 大顶堆求最小K个数 15 typedef multiset<int, greater<int> > intSet; 16 typedef multiset<int, greater<int> >::iterator setIterator; 17  18 void GetKLeastNumbers2(int* data, intSet& leastNumbers, int length, int k) 19 { 20     leastNumbers.clear(); 21      22     if (k<1 || length<k) 23         return; 24      25     for (int i = 0; i < length; ++i) 26     { 27         if (leastNumbers.size() < k) 28             leastNumbers.insert(data[i]); 29          30         else 31         { 32             setIterator Greatest = leastNumbers.begin(); 33             if (data[i] < *(leastNumbers.begin())) 34             { 35                 leastNumbers.erase(Greatest); 36                 leastNumbers.insert(data[i]); 37             } 38         } 39     } 40      41     for (setIterator iter = leastNumbers.begin(); iter != leastNumbers.end(); ++iter) 42     { 43         printf("%d ", *iter);  44     } 45     printf("\n"); 46 } 47  48  49 void swap(int* p, int* q) 50 { 51     int temp = *p; 52     *p = *q; 53     *q = temp; 54 } 55  56 // Partition函数应用 57 int Partition(int* data, int length, int start, int end) 58 { 59     if (data=http://www.mamicode.com/=NULL || length<=0 || start<0 || end>=length) 60         return -1; 61      62     // 令数组第一个数字为标杆 63     int index = start;                 64      65     // 标杆与数组最后一个元素交换 66     swap(&data[index], &data[end]); 67      68     int small = start - 1; 69     for (index = start; index < end; ++index) 70     { 71         if (data[index] < data[end]) 72         { 73             ++ small; 74             if (small != index) 75             { 76                 swap(&data[index], &data[small]); 77             } 78         } 79     } 80     ++ small; 81     swap(&data[small], &data[end]); 82      83     return small; 84 } 85  86 // 利用Partiton实现快排 87 void quickSort(int* data, int length, int start, int end) 88 { 89     if (start==end || data=http://www.mamicode.com/=NULL || length<=0) 90         return; 91      92     int index = Partition(data, length, start, end); 93     // printf("index is %d\n", index); 94     if (index > start) 95         quickSort(data, length, start, index-1); 96     if (index < end) 97         quickSort(data, length, index+1, end); 98 } 99 100 // 利用Partition寻找出现次数超过一半的数 (中位数)101 int GetMoreThanHalf(int* input, int length)102 {103     if (input==NULL || length<=0)104         return -1;105     int start = 0;106     int end   = length - 1;107     int index = Partition(input, length, start, end);108     int middle = length >> 1;109     while (index != middle)110     {111         if (index > middle)112         {113             end = index - 1;114             index = Partition(input, length, start, end);115         }116         else117         {118             start = index + 1;119             index = Partition(input, length, start, end);120         }121     }122     int ret = input[middle];123     // 检验是否正确124     int count2 = 0;125     for (int i = 0; i < length; ++i)126     {127         if (input[i] == ret)128             count2 ++;129     }130     if (count2*2 > length)131     {132         printf("middle number is %d\n", input[middle]);133         return ret;134     }135     else136     {137         printf("Not Find\n");138         return -1;139     }140 }141 142 143 // 利用Partition寻找第K小的数144 int GetKthNumber(int* input, int length, int k)145 {146     if (input==NULL || length<=0 || k<=0 || k>length)147         return -1;148     int start = 0;149     int end   = length - 1;150     int index = Partition(input, length, start, end);151     while (index != k - 1)152     {153         if (index > k-1)154         {155             end = index-1;156             index = Partition(input, length, start, end);157         }158         else159         {160             start = index + 1;161             index = Partition(input, length, start, end);162         }163     }164     printf("Kth is %d\n", input[index]);165     return input[index];166 }167 168 169 // 利用Partition寻找最小K个数170 void GetKLeastNumbers(int* input, int length, int* output, int k)171 {172     if (input==NULL || output==NULL || length<=0 || k<=0 || k>length)173     {174         return;175     }176     int start = 0;177     int end   = length - 1;178     int index = Partition(input, length, start, end);179     while (index != k - 1)180     {181         if (index > k-1)182         {183             end = index - 1;184             index = Partition(input, length, start, end);185         }186         else187         {188             start = index + 1;189             index = Partition(input, length, start, end);190         }191         // printf("index is %d\n", index);192     }193     for (int i = 0; i < k; ++i)194         output[i] = input[i];195     196     for (int i = 0; i < k; ++i)197         printf("%d ", output[i]);198     printf("\n");199 }200 201 // 利用大顶堆寻找最小K个数202 203 204 int main()205 {206     int k = 5;207     int nums[] = {3,5,5,5,6,5,7,1,2,9};208     int length = 10;209     int output[k] = {0};210     211     // 快速排序212     quickSort(nums, length, 0, length-1);213     for (int i = 0; i < length; ++i)214         printf("%d ", nums[i]);215     printf("\n");216     217     // 求最小K个数218     GetKLeastNumbers(nums, length, output, k);219     220     // 求第K大的数221     GetKthNumber(nums, length, k);222     223     // 求数组中超过一半的数(中位数)224     GetMoreThanHalf(nums, length);225     226     // 大顶堆求最小K个数227     intSet leastNumbers;228     GetKLeastNumbers2(nums, leastNumbers, length, k);229 }