分治-快排-面试题 17.14.最小k个数-力扣(LeetCode)

一、题目解析

1、返回k个最小数

2、可以任意顺序

二、算法原理

解法1：排序 O(N*logN)

直接排序数组，然后用迭代器初始化构造一个匿名对象

解法2：大根堆 O(N*logk)

构造一个大根堆，依次插入元素，控制容器大小为k，超过k的部分pop掉，最后大根堆中存储的就是k个最小的元素，插入到vector中

解法3：快排

随机基准元素+数组分三块

详细见该篇文章分治-快排-215.数组中的第k个最大元素-力扣(LeetCode)-CSDN博客

根据三块区域元素个数分情况讨论

三、代码示例

解法1：

 //解法1：排序
    vector<int> smallestK(vector<int>& arr, int k)
    {
        sort(arr.begin(),arr.end());
        return {arr.begin(),arr.begin()+k};
    }

解法2：

//解法2：大根堆
    vector<int> smallestK(vector<int>& arr, int k)
    {
        if(k == 0 || arr.empty()) return {};
        priority_queue<int> pq;
        for(auto e : arr)
        {
            pq.push(e);
            if(pq.size()>k) pq.pop();
        }
        vector<int> ret;
        while(k--)
        {
            ret.push_back(pq.top());
            pq.pop();
        }
        return ret;
    }

解法3：

//解法3：快排
    vector<int> smallestK(vector<int>& arr, int k)
    {
        srand(time(NULL));
        if(k==0 || arr.empty()) return {};
        qsort(arr,k,0,arr.size()-1);
        return {arr.begin(),arr.begin()+k};
    }
    void qsort(vector<int>& arr,int k,int l,int r)
    {
        if(l>=r) return;

        int key = getRandom(arr,l,r);//随机选择基准元素
        int left = l-1,right = r+1,i = l;//数组分三块
        while(i<right)
        {
            if(arr[i]<key) swap(arr[++left],arr[i++]);
            else if(arr[i] == key) i++;
            else swap(arr[i],arr[--right]);
        }
        int a = left - l +1,b = right - left - 1;//分情况讨论
        if(a>k) qsort(arr,k,l,left);
        else if(a+b>=k) return;
        else qsort(arr,k-a-b,right,r);
    }
    int getRandom(vector<int>& arr,int left,int right)
    {
        return arr[rand() % (right-left+1) + left];
    }

看到最后，如果对您有所帮助，还请点赞、收藏和关注，我们下期再见！