求最小的K个数的三种方法

最小的K个数
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

1、最简单
全排序。利用各种排序方法，比如冒泡，快速排序，归并排序、希尔排序等。（关于几种排序方法可以仔细学一遍）。复杂度要么n平方，最好也是nlogn。代码就不写了。

2、堆排序
建立一个容量为k的大根堆的优先队列。遍历一遍元素，如果队列大小<k,就直接入队，否则，让当前元素与队顶元素相比，如果队顶元素大，则出队，将当前元素入队。
大根堆用于升序排序（所以求最小的前k个数用大根堆）。堆排序的时间复杂度是O(Nlogk)，空间复杂度是O(1),所以在海量数据及内存不足的条件下，该排序方法适用。
优先队列的底层是用堆来实现的。大根堆就是父节点比子节点大的完全二叉树。C++中STL中的优先队列默认的是大根堆，如果要用小根堆则需要加入greater.

priority_queue<Type, Container, Functional>Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector，因为玩完全二叉树用数组比较好表示），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。如果要用小根堆则需要加入greater

//升序队列
priority_queue <int,vector,greater > q; 小根堆
//降序队列
priority_queue <int,vector,less >q; 大根堆
所以求最小的K个数要用降序队列，即根是最大的，之后每个数和根比较，如果更大，直接略过，比根小，把根删去，把这个数加进去。

lass Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        if(k==0||k>input.size())
            return ans;
        priority_queue<int,vector<int>,less<int>> pq;
        for(int i=0;i<input.size();i++)
        {
            if(pq.size()<k)
                pq.push(input[i]);
            else
            {
                if(input[i]>pq.top())
                    continue;
                else
                {
                    pq.pop();
                    pq.push(input[i]);
                }
            }
        }
        while(!pq.empty())
        {
            ans.push_back(pq.top());
            pq.pop();
        }
        return ans;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

第三种利用快排，可能思考有难度，就不推荐了，但是时间复杂度是O(N)。