[剑指Offer] 29.最小的K个数

【思路1】全排序（快排）之后取出前K个数。O(K+nlogn)

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

【思路2】冒泡排序的思想，但不用全排序，只要找出K个即可

 1 class Solution
 2 {
 3 public:
 4     void swap(int& x,int& y)
 5     {
 6         int temp = x;
 7         x = y;
 8         y = temp;
 9     }
10     vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
11     {
12         vector<int> res;
13         int size = input.size();
14         if(k > size)
15             return res;
16         for(int i = 0; i < k; i ++)
17         {
18             for(int j = 0; j < size - i - 1; j ++)
19             {
20                 if(input[j + 1] > input[j])
21                 {
22                     swap(input[j + 1],input[j]);
23                 }
24             }
25             res.push_back(input[size - i - 1]);
26         }
27         return res;
28     }
29 };