剑指offer40:最小的k个数

还记得剑指offer39:数组中出现次数超过一半的数那道题吗，其实异曲同工，只不过k可以取任意一个值，那么我们一样可以用快排来做：

class Solution {
public:
    vector getLeastNumbers(vector& arr, int k) {
        if(arr.empty()) return {};
        quickSort(arr,0,arr.size()-1,k);
        vector ans;
        for(int i=0;i &arr,int left,int right,int k)
    {
        if(left>=right) return;
        int loc=partition(arr,left,right);
        int nums=loc-left+1;
        if(nums==k)
        {
            return;
        }
        else if(nums>k)
        {
            quickSort(arr,left,loc-1,k);
        }
        else
        {
            quickSort(arr,loc+1,right,k-nums);
        }
    }


    int partition(vector &arr,int left,int right)
    {
        int pivot=arr[left];
        int l=left,r=right+1;
        while(true)
        {
            while(lleft&&arr[--r]>pivot);
            if(l>=r) break;
            swap(arr[l],arr[r]);
        }
        swap(arr[left],arr[r]);
        return r;
    }

};

最后结果：

还有一点和剑指offer39的快排做法不一样的一些细节：

传入的k和39中的mid意义是不一样的，k是用来计数，而mid是指位置，k在递归过程中可以变，而mid是恒定的。这里你可能会问，那可不可以也按照位置来呢，那当然是可以的，做法也是一样的

把quickSort改成下面这样就行：

    void quickSort(vector &arr,int left,int right,int k)
    {
        if(left>=right) return;
        int loc=partition(arr,left,right);
        // int nums=loc-left+1;
        if(loc==k)
        {
            return;
        }
        else if(loc>k)
        {
            // quickSort(arr,left,loc-1,k);
            quickSort(arr,left,loc-1,k);
        }
        else
        {
            // quickSort(arr,loc+1,right,k-nums);
            quickSort(arr,loc+1,right,k);
        }
    }

 对这种方法的一点点分析：

时间复杂度：快排O（nlogn）

这里的缺点是改变了原数组

当然，强大的C++还有自己的api可以直接调用，直接cv：

class Solution {
public:
    vector getLeastNumbers(vector& arr, int k) {
        vector vec(k, 0);
        sort(arr.begin(), arr.end());
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这里值得学习的或许就是这个sort的调用。

在书里和官方都提供了一种堆排序的方法，书里面说这特别适合大数据量的排序，是这样的：由于内存是有限的，所以我们如果用快排，对大数据量可能在内存里放不下。而针对题目中这个特定的问题，我们可以维护一个大小为k的最大堆，那我们可以每次对一个数进行操作：

1.如果堆中元素少于k个，直接插入

2.如果堆中元素满了，判断当前元素和堆顶元素的大小关系，如果当前的更大，进行下一个元素的判断，如果更小，则弹出堆顶，再压入当前元素

最后等遍历完，最小的k个元素就在这个堆里面了。

优点：复杂度减小为O(nlogk)，而且每次只要取一个数，加上这个堆的空间，在数据量特别大的时候这样的方法还能节省内存的空间

class Solution {
public:
    vector getLeastNumbers(vector& arr, int k) {
        vector ans;
        if(k==0) return ans;
        priority_queueQ;
        for(int i=0;i 
结果如下所示：
 
 
 有些东西是值得积累一下的：
 
C++中的优先队列priority_queue