题解 | #最小的K个数#

/*
描述
给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
0 <= k <= input.length <= 10000
0 <= input[i] <= 10000
Main idea:
最好的方法是使用大小为k的大项堆，遍历数组的每个元素，若该元素小于堆顶，则替换堆顶并进行percolate down（时间复杂度为log k)，维持大项堆。
最终返回该大项堆即可，总的时间复杂度为：O(nlog(k))
此处用vector代替大项堆，每次替换堆顶后进行sort最简单，此时总的时间复杂度为：O(n* klog(k))，当n足够大时，性能是要比直接sort原数组：O(nlog(n))要好的
Note:
每次替换堆顶后进行插入排序也简单，此时时间复杂度为： O(nk)
*/

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        // O(n* k*log(k))
        if (k > input.size() || k == 0)
            return vector<int>{};
        vector<int> hp(input.begin(), input.begin() + k);
        sort(hp.begin(), hp.end());
        for (int i = k; i < input.size(); ++i) {
            if (input[i] < hp[k - 1]) {
                hp[k - 1] = input[i];
                sort(hp.begin(), hp.end());
            }
        }
        return hp;
    }

    vector<int> GetLeastNumbers_Solution_1(vector<int> input, int k) {
        // O(n*k)
        if (k > input.size() || k == 0)
            return vector<int>{};
        vector<int> hp(input.begin(), input.begin() + k);
        int i, j;
        sort(hp.begin(), hp.end());
        for (i = k; i < input.size(); ++i) {
            if (input[i] < hp[k - 1]) {
                hp[k - 1] = input[i];
                for (j = k - 2; j >= 0; j--) {
                    if (hp[j] > input[i]) {
                        hp[j + 1] = hp[j];
                        continue;
                    }
                    hp[j + 1] = input[i];
                    break;
                }
                if (j < 0)
                    hp[0] = input[i];

            }
        }
        return hp;
    }

    vector<int> GetLeastNumbers_Solution_2(vector<int> input, int k) {
        // O(nlog(n))
        sort(input.begin(), input.end());
        return k <= input.size() ? vector<int>(input.begin(), input.begin() + k) : vector<int>{};
    }
};