思路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 }
