最小的K個數

題目:輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。

思路1:我們通過快排找到第k個數，然後比他的小的都在左邊，比他大的都在右邊。

思路2:應對大數據的情況，首先取數組中前k個數字建立大根堆，建立堆之後，從第k+1個元素開始，和堆頂元素進行比較，如果小於堆頂的元素，那麼就替換堆頂的元素

  1 #include "stdafx.h"
  2 #include<iostream>
  3 #include<set>
  4 #include<vector>
  5 #include<stdlib.h>
  6 #include<tchar.h>
  7 #include<exception>
  8 using namespace std;
  9 
 10 int RandomInRange(int min, int max)
 11 {
 12     int random = rand() % (max - min + 1) + min;
 13     return random;
 14 }
 15 
 16 void Swap(int* num1, int* num2)
 17 {
 18     int temp = *num1;
 19     *num1 = *num2;
 20     *num2 = temp;
 21 }
 22 
 23 int Partition(int data[], int length, int start, int end)
 24 {
 25     if(data == NULL || length <= 0 || start < 0 || end >= length)
 26         //throw std::exception("Invalid Parameters");
 27         exit(1);
 28 
 29     int index = RandomInRange(start, end);
 30     Swap(&data[index], &data[end]);
 31 
 32     int small = start - 1;
 33     for(index = start; index < end; ++ index)
 34     {
 35         if(data[index] < data[end])
 36         {
 37             ++ small;
 38             if(small != index)
 39                 Swap(&data[index], &data[small]);
 40         }
 41     }
 42 
 43     ++ small;
 44     Swap(&data[small], &data[end]);
 45 
 46     return small;
 47 }
 48 
 49 //=====================方法1====================== 
 50 void GetLeastNumbers_Solution1(int* input, int n, int* output, int k)
 51 {
 52     if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
 53         return;
 54     
 55     int start = 0;
 56     int end = n - 1;
 57     int index = Partition(input, n, start, end);
 58     while(index != k - 1)
 59     {
 60         if(index > k - 1)
 61         {
 62             end = index - 1;
 63             index = Partition(input, n , start, end);
 64         }
 65         else
 66         {
 67             start = index + 1;
 68             index = Partition(input, n, start, end);
 69         }
 70     }
 71     
 72     for(int i = 0; i < k; ++i)
 73         output[i] = input[i];
 74 }
 75 
 76 //====================方法2======================
 77 typedef multiset<int, greater<int> >            intSet;
 78 typedef multiset<int, greater<int> >::iterator  setIterator;
 79 
 80 void GetLeastNumbers_Solution2(const vector<int>& data, intSet& leastNumbers, int k)
 81 {
 82     leastNumbers.clear();
 83     
 84     if(k < 1 || data.size() < k)
 85         return;
 86     
 87     vector<int>::const_iterator iter = data.begin();
 88     for(; iter != data.end(); ++iter)
 89     {
 90         if((leastNumbers.size()) < k) 
 91             leastNumbers.insert(*iter);
 92             
 93         else
 94         {
 95             setIterator iterGreatest = leastNumbers.begin();
 96             
 97             if(*iter < *(leastNumbers.begin()))
 98             {
 99                 leastNumbers.erase(iterGreatest);
100                 leastNumbers.insert(*iter);
101             }
102         }
103     }
104 }
105 
106 int main()
107 {
108     
109     int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
110     int length = sizeof(data) / sizeof(int);
111     int k  = 4;
112     
113     printf("The data is:\n");
114     for(int i = 0 ; i < length ; ++i)
115         printf("%d\t", data[i]);
116     printf("\n\n");
117     
118     vector<int> vectorData;
119     for(int i = 0; i < length ; ++i)
120         vectorData.push_back(data[i]);
121         
122     printf("Result for solution1:\n");
123     
124     int* output = new int[k];
125     GetLeastNumbers_Solution1(data, length, output, k);
126     
127     for(int i = 0 ; i < k ; ++i)
128         printf("%d\t", output[i]);
129     printf("\n\n");
130 
131     delete[] output;
132     
133     printf("Result for solution2:\n");
134     
135     intSet leastNumbers;
136     GetLeastNumbers_Solution2(vectorData, leastNumbers, k);
137     
138     printf("The actual output numbers are:\n");
139     
140     for(setIterator iter = leastNumbers.begin(); iter != leastNumbers.end(); ++iter)
141         printf("%d\t", *iter);
142     printf("\n\n");
143 
144     
145     return 0;
146 }