面试题 17.14. 最小K个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

方法一：优先级队列

先取前四个，默认最大堆排序，从第k个开始比较 小就放入队列，大就不要，再传入数组里，输出数组

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        if(arr.size() == 0 || k <= 0) return {};
        priority_queue<int>que;
        vector<int> res;
        for(int i = 0;i < k;i++){
            que.push(arr[i]);
        } 
        for(int i = k;i < arr.size();i++){
            if(arr[i] < que.top()){
                que.pop();
                que.push(arr[i]);
            }
        }
        while(!que.empty()){
            res.push_back(que.top());
            que.pop();
        }
        return res;
    }
};

方法二：堆排序

class Solution {
public:
    void adjust(vector<int>& arr,int start,int end)
    {
           int father = start;
           int child = father * 2 + 1;
           while(child <= end)
           {
                if(child + 1 <= end && arr[child] < arr[child + 1]) child++;
                if(arr[child] > arr[father]) 
                {
                    swap(arr[child] , arr[father]);
                    father = child;
                    child = father * 2 + 1;
                }
                else 
                {
                    break;
                }
           } 
    }
    vector<int> smallestK(vector<int>& arr, int k) {
        if(arr.size() == 0 || k <= 0) return  {};
        for(int i = k / 2 - 1;i >= 0;i--)
        {
            adjust(arr,i,k - 1);
        }
        for(int i = k;i < arr.size();i++)
        {
            if(arr[0] > arr[i])
            {
               swap(arr[0] , arr[i]);
               adjust(arr,0,k-1);
            }
        }
        vector<int> res;
        for(int i = 0 ;i < k;i++)
        {
            res.push_back(arr[i]);
        }
        return res;
    }
};

方法三：快速排序

class Solution {
public:
    int Quick(vector<int> &arr, int L, int R){
        int i = L - 1;
        int j = R + 1;
        int index = L;
        int temp = arr[L];
        while(index < j){
            if(arr[index] > temp) swap(arr[--j], arr[index]);
            else if (arr[index] < temp) swap(arr[++i], arr[index++]);
            else index++;
        }
        return i + 1;
    }
    void Quicksort(vector<int>&arr, int L , int R , int k){
        if(L > R) return;
        int p = Quick(arr, L, R);
        if(p > k) Quicksort(arr,L, p - 1, k);
        else if(p< k) Quicksort(arr, p + 1, R, k);
        else return;
    }
    vector<int> smallestK(vector<int>& arr, int k) {
        if(arr.size() == 0 || k == 0) return{};
        Quicksort(arr, 0, arr.size() - 1, k);
        vector<int> res;
        for(int i = 0; i < k; i++){
            res.push_back(arr[i]);
        }
        return res;
    }
};