LeetCode每日一题———面试题40. 最小的k个数

一

今天这个题乍一看是个排序题，找到最小的k个数，正好最近数据结构学到了拍戏，但是也只学了插入排序，先咔咔整上去！ 算法复杂度那肯定是O（n^2）了，当然也可以优化到O（n*k），懒得再写了…
当然其他排序更快的算法也可以，比如快速排序，但是还没看到这块所以就没写了。

class Solution {
public:
   vector<int> getLeastNumbers(vector<int>& arr, int k) {
        for(int i = 1;i<arr.size();i++){
            if(arr[i] < arr[i-1]){
                int j = i-1;
                int x = arr[i];
                while(j>-1 && arr[j] > x){
                    arr[j+1] = arr[j];
                    j--;
                }
                arr[j+1] = x;
            }      
        }
        return vector<int>(arr.begin(),arr.begin()+k);
    }
}；

二

然后学习了一下官方的解法，也就是用堆排序，算法复杂度O（n*logk）。
之前没有接触过堆，发现堆排序其实就是完全二叉树排序，树中保证了父子的大小有序，大根堆是根节点值最大，往下按层变小，小根堆相反。但是不保证左右节点之间的大小关系。

我们用一个大根堆实时维护数组的前 k 小值。首先将前 k个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。在下面的代码中，由于 C++ 语言中的堆（即优先队列）为大根堆，我们可以这么做。而 Python 语言中的对为小根堆，因此我们要对数组中所有的数取其相反数，才能使用小根堆维护前 k 小值。

解法一：

由于 C++ 语言中的堆（即优先队列）为大根堆，用priority_queue来实现。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int>vec(k, 0);
        if (k == 0) return vec; // 排除 0 的情况
        priority_queue<int>Q;          //优先队列
        for (int i = 0; i < k; ++i) Q.push(arr[i]);   //先插入k个元素
        for (int i = k; i < (int)arr.size(); ++i) {          //如果顶部元素比插入元素更大，就把顶部元素剔除，插入更小的新元素
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;  //return vector<int>(arr.begin(), arr.begin()+k);
    }
};

解法二：

学习了一起做题的同学自己构造的简单堆排序，其实也是按照完全二叉树的性质，利用下标来完成插入元素与根部元素的比较。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(k==0)
            return vector<int>(0);
        vector<int> max(k+1,INT_MAX);
        for(int n:arr)     //max[0]用来当交换数据的temp，max[1]为根节点，也就是最大值
            if(n<max[1]){    //如果插入元素比根节点的元素还要小，那么根节点原来的值就剔除，变为新的插入元素
                int i=1;
                max[1]=n;
                while(2*i<k+1){    //下标由1开始，所以当前树中的节点数=2*i-1，节点数<k相当于 2*i<k+1
                    int j;
                    if((2*i+1)<k+1)    //2*i就是左孩子节点，2*i+1是右孩子，找到孩子节点的最大值与插入元素（父节点值）比较
                        j=max[2*i]>max[2*i+1]?(2*i):(2*i+1);
                    else
                        j=2*i;
                    if(max[i]<max[j]){    //如果孩子节点比父节点大，就交换继续往下比较，直到找到插入元素能安放的位置
                        max[0]=max[j];
                        max[j]=max[i];
                        max[i]=max[0];
                        i=j;
                    }
                    else
                        break;
                }
            }
        return vector<int>(max.begin()+1,max.end());
    }
};