题解 | 最小的K个数

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        // write code here
        vector<int> res;
        //条件一个是错误一个是空，不一样
        if(input.size()<k||k==0) return res;
        
        sort(input.begin(), input.end());//手写快排试试呢，还有一个比较器greater
        //直接返回这个vector的子集会更省一点 return vector<int>({input.begin(), input.begin()+k}); 
        for(int i = 0; i < k; ++i){
            res.emplace_back(input[i]);
        }
        return res;
    }
};

方法一：

排序非常直观，要考虑没有k个的情况和为空时的情况，边界条件很重要。

#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        // write code here
        vector<int> res;
        if(input.size()<k||k==0) return res;
        res.resize(k);
        priority_queue<int> pq;
        for(const int& u:input){
            if(pq.size()<k){
                pq.push(u);
            }
            else{
                if(pq.top()>u){
                    pq.pop();
                    pq.push(u);
                }
            }
        }
        for(int i = k-1; i >= 0; --i){
            res[i] = pq.top();
            pq.pop();
        }
        return res;
    }
};

方法二：堆

这里涉及到一个通用模板的问题，我们都知道为了保持库的通用性会使用传迭代器和传lambda函数等方法，priority_queue也是一个通用模板，它要用的话必须实现比较器，这也是通常有大根堆、小根堆两种堆的原因。（如果想要知道更多模板相关可以私信我）

默认为大根堆，如果想使用小根堆，就要在priority_queue的模板参数中加上一个std::greater<int>（当然别忘了vector<int>)，这里用大根堆很方便。

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    
    int returnPos(vector<int>& input, int l, int r){
        //根据题意和我的代码设置，此处不用判错
        //双指针法
        int val = input[r];
        int pos = l;
        for(int i = l; i < r; ++i){
            if(input[i]<val){
                swap(input[pos], input[i]);
                ++pos;
              //  std::cout<<pos<<std::endl;
            }
        }
        //就算是同一个也没关系吗？swap的库函数是怎么实现的？
        swap(input[pos], input[r]);
        return pos;
    }
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        // write code here
        vector<int> res;
        //一个是有问题一个是空，不一样，虽然都返回空vector数组
        if(input.size()<k||k==0) return res;
        int l = 0, r = input.size()-1;
        while(l<=r){
            int valPos = returnPos(input, l, r);
            //初始化列表的语法，爱来自伟大的模板
            if(valPos==k-1||valPos==k) return vector<int>({input.begin(), input.begin()+k});
            else if(valPos<k-1){
                l = valPos+1;
            }
            else{
                r = valPos-1;
            }
        }
        return res;
    }
};

方法三（快速排序）：

这道题只要前k个，但是不用排序，很容易想到快排，因为它在一次遍历的时候就是分成前一部分和后一部分，前小后大以分界位置的值为分隔的。

常用双指针，但是我感觉没必要这样说，容易引起初学者的恐慌。

其实就是找到一个小于分界值的就往前面放。

怎么找呢？用另一个指针从头开始遍历，直到放到分界值位置（最后一位）前一位。这样所有的都被找过一遍了。

怎么放呢？前面的那个指针只有放的时候才动，它指的位置就是下一个可以放的位置，被放后就要往后加一。

因为我们是为了排序而不是破坏，所以不只是放而是交换，这样可以保留数据。

最后我们把所有的都排了，然后放的指针指向了比分界值小的最后一位的下一位。

我们此时需要把分界值的位置换到放的指针所指向的位置（你知道的，因为它是分界值），也是交换。

有时放的指针指向的就会是分界值所在位置，但是没关系，原地swap也是可以的。