题目链接

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

解题思路

排序

直接排序，然后去前k小数据。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if (k==0 || k>input.size()) return ret;
        sort(input.begin(), input.end());
        return vector<int>({input.begin(), input.begin()+k});   
    }
};
// 或者
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if(input.empty()||k>input.size())
            return ret;
        sort(input.begin(), input.end());
        for(int i=0;i<k;i++){
            ret.push_back(input[i]);
        }
        return ret;
    }
};

时间复杂度：O(nlongn)
空间复杂度：O(1)

大小为 K 的最小堆

特别适合处理海量数据

建立一个容量为k的大根堆的优先队列。遍历一遍元素，如果队列大小大根堆的根为当前堆的最大值。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if (k==0 || k > input.size()) return ret;
        priority_queue<int, vector<int>> pq;
        for (const int val : input) {
            if (pq.size() < k) {
                pq.push(val);
            }
            else {
                if (val < pq.top()) {
                    pq.pop();
                    pq.push(val);
                }

            }
        }

        while (!pq.empty()) {
            ret.push_back(pq.top());
            pq.pop();
        }
        return ret;
    }
};
// 或者
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if(input.empty()||k>input.size())
            return ret;
        priority_queue<int> pq;
        for(const int item : input){
            pq.push(item);
            if(pq.size()>k)
                pq.pop();
        }
        // 存入 ret,从大到小
        while(!pq.empty()){
            ret.push_back(pq.top());
            pq.pop();
        }
        // 反转ret,从小到大
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
//或者
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()<k)
            return {};
        priority_queue<int,vector<int>,greater<int>> pq;
        for(const int i:input){
            pq.push(i);
        }
        vector<int> res;
        while(k--){
            res.push_back(pq.top());
            pq.pop();
        }
        return res;
    }
};

时间复杂度：O(nlongk), 插入容量为k的大根堆时间复杂度为O(longk), 一共遍历n个元素
空间复杂度：O(k)

快速选择

复杂度：O(N) + O(1)
只有当允许修改数组元素时才可以使用
只是最小的前K个数，顺序不是从小到大的

对数组[l, r]一次快排partition过程可得到，[l, p), p, [p+1, r)三个区间,[l,p)为小于等于p的值
[p+1,r)为大于等于p的值。
然后再判断p，利用二分法

如果[l,p), p，也就是p+1个元素（因为下标从0开始），如果p+1 == k, 找到答案
如果p+1 < k, 说明答案在[p+1, r)区间内，
如果p+1 > k , 说明答案在[l, p)内

class Solution {
public:
    int partition(vector<int> &input,int l,int r){
        // 下标为l到r-1
        int pivot = input[r-1];
        int i=l;
        // 以最后一个数为基准数
        // 小于最后一个数的都依次与前面的数交换
        for(int j=l;j<r-1;j++){
            if(input[j]<pivot){
                swap(input[i++], input[j]);
            }
        }
        // 将基准数交换到都小于它的数的后面
        // 当前序号i之前的数都小于input[i],i之后的数都大于input[i]
        swap(input[i], input[r-1]);
        return i;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if(input.empty()||k>input.size())
            return ret;
        int l=0,r=input.size();
        while(l<r){
            int p = partition(input,l,r);
            // 正好是前k个数
            if(p+1 == k){
                return vector<int>(input.begin(),input.begin()+k);
            }
            // 前k个数未全，答案在[p+1, r)区间内还有，
            if(p+1 < k){
                l = p+1;
            }
            // 前q+1个数过多，答案在[l, p)内
            else{
                r=p;
            }
        }
        // 未找到返回空数组
        return ret;
    }
};

算法(leetcode 牛客网)

40. 最小的 K 个数

题目链接

题目描述

解题思路

排序

大小为 K 的最小堆

快速选择