30 最小的k个数

输入n个整数，找出其最小的k个数，例如输入4,5,1,6,2,7,3,8，最小的4个数为1,2,3,4

解法一：快排思想，会改变原数组 O（n）

注意是vector<int>&

C++:

 1 class Solution {
 2 public:
 3     int Partition(vector<int>& input, int left , int right){
 4         int k = left ;
 5         for (int i = left ; i < right ; i++){
 6             if (input[i] < input[right]){
 7                 if (k!=i)
 8                     swap(input[i],input[k]) ;
 9                 k++ ;
10             }
11         }
12         swap(input[right],input[k]) ;
13         return k ;
14     }
15     
16     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
17         int len = input.size() ;
18         vector<int> output ;
19         if (k > len || k<=0)
20             return output ;
21         int left = 0 ;
22         int right = len - 1 ;
23         int index = Partition(input,left,right) ;
24         while(index != k-1){
25             if (index > k-1){
26                 right = index - 1 ;
27                 index = Partition(input,left,right) ;
28             }else{
29                 left = index + 1 ;
30                 index = Partition(input,left,right) ;
31             }
32         }
33         for (int i = 0 ; i < k ; i++)
34             output.push_back(input[i]) ;
35         return output ;
36     }
37 };

解法二：维护一个大小为k的容器，每次将容器中最大的数字用小数字替换掉
O（nlogk）
如果有海量数据，没法一次放入内存中，可用这种方法
可用大顶堆或者红黑树

C++:

 1 class Solution {
 2 public:
 3     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
 4         int len = input.size() ;
 5         if (k > len || k <= 0)
 6             return vector<int>() ;
 7         multiset<int,greater<int> > res ;
 8         for(int num : input){
 9             if (res.size() < k){
10                 res.insert(num) ;
11             }else{
12                 if(num < *(res.begin())){
13                     res.erase(*(res.begin())) ;
14                     res.insert(num) ;
15                 }
16             }
17         }
18         return vector<int>(res.begin() , res.end()) ;
19     }
20 };

java:

 1 import java.util.ArrayList;
 2 import java.util.PriorityQueue;
 3 public class Solution {
 4    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
 5        if (k > input.length || k <= 0)
 6            return new ArrayList<Integer>() ;
 7        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2) -> o2-o1) ;
 8        for(int num : input){
 9            if (maxHeap.size() < k){
10                maxHeap.add(num) ;
11            }else{
12                if (num < maxHeap.peek()){
13                    maxHeap.poll() ;
14                    maxHeap.add(num) ;
15                }
16            }
17        }
18        return new ArrayList<Integer>(maxHeap) ;
19    }
20 }