剑指offer29：最小的k个数

 1 class Solution {
 2 public:
 3     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
 4         sort(input.begin(),input.end());
 5         vector<int> result;
 6         if(k>input.size())
 7             return result;
 8         for(int i = 0;i<k;i++){
 9             result.push_back(input[i]);
10         }
11         return result;
12     }
13 };

 1 class Solution {
 2 public:
 3     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
 4         // 必须检查k的大小否则出错！！！
 5         if (input.size() == 0 || k > input.size() || k<=0) 
 6             return vector<int>();
 7        
 8         int start = 0;
 9         int end = input.size() -1;
10         int index = Partition(input,start,end);
11         while(index != k-1){
12             if(index < k-1){
13                 start = index + 1;  // k在index右边
14                 index = Partition(input,start,end);
15             }
16             else{
17                 end = index -1;     // k在index左边
18                 index = Partition(input,start,end);
19             }
20         }
21         vector<int> ret;
22         for (int i = 0; i < k; ++i) {
23             ret.push_back(input[i]);
24         }
25         return ret;
26     }
27 
28     int Partition(vector<int> &data, int start, int end){
29         if(start > end)
30             return start;
31 
32         int key = data[start];  // 取第一个值为参考值
33         while(start< end){
34             while(data[end] >= key && start < end) end--;
35             data[start] = data[end];
36             while(data[start] <= key && start<end) start++;
37             data[end] = data[start];
38         }
39         data[start] = key;
40         return start;
41     }
42 };