题解 | #最小的K个数#

jz29 最小的K个数

题意分析

找出数组中最小的K个数

示例输入：input = [4,5,1,6,2,7,3,8]，4
返回：[1,2,3,4]
解释：很明显输入数组最小的4个元素为1,2,3,4。

题解一（堆）

堆可以看做是一个二叉树。其父节点和子节点有这一定的数量关系。

大根堆：也叫最大堆，每个父节点大于其子节点。

小根堆：也叫最小堆：每个父节点小于其子节点。

对于本题，我们使用最大堆。在c++中，可以使用 priority_queue作为声明一个大根堆。

算法过程：首先将input数组前k个数插入到大根堆中，之后的数依次和大根堆的堆顶进行比较。如果当前的数比堆顶的数要小，那么就把堆顶的弹出，把当前的数插入。如果比堆顶的元素大，pass这个当前的数。

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    if (k == 0 || k>input.size()) {
        return {};
    }
    priority_queue<int> q;
    for (int i = 0; i < k; ++i) {
        q.push(input[i]);
    }
    for (int i = k; i < input.size(); ++i) {
        if (q.top() > input[i]) {
            q.pop();
            q.push(input[i]);
        }
    }
    vector<int>ret(k,0);
    for(int i=0;i<k;i++) {
        ret[i] = q.top();
        q.pop();
    }
    return ret;

}

时间复杂度: $O(nlg\ k)$ 。对优先队列做一次插入时间复杂度为 $O(lg \ k)$ 。最坏的情况n个数都要插入到优先队列中，总的时间复杂度为 $O(nlg \ k)$ 。

空间复杂度: $O(k)$ 。使用了大小为k的优先队列

题解二（快排的Select 部分）

快排的划分函数会根据Pivot元素将输入数组分成两部分。小于Pivot会放在左边，大于Pivot会放在右边。然后返回Pivot的下标。

我们可以使用一次划分函数，划分一次。
如果划分后的index小于K，说明在Pivot的右边还有需要的元素，接着使用划分函数。
如果划分后的index大于K，说明在Pitvo的左边还有需要的元素，接着使用划分函数。
举个例子：
input = [4,5,1,6,2,7,3,8]，4
找到前4个数
图片说明

int partition(vector<int>& input, int l, int r) {
     //以l-r区间的最后一个元素作为pivot划分
    int pivot = input[r];
    int i = l - 1;
    for (int j = l; j <= r - 1; ++j) {
        if (input[j] <= pivot) {
            i = i + 1;
            //小于pivot与pivot发生交换
            swap(input[i], input[j]);
        }
    }
    swap(input[i + 1], input[r]);
    //返回小于pivot的第一个元素的下标
    return i + 1;
}

void selected(vector<int>& input, int l, int r, int k) {
    //选择部分，选择input的l-r区间的前k小的数
    if (l >= r) {
        return;
    }
    int pos = partition(input, l, r);
    int num = pos - l + 1;
    if (k == num) {
        //当划分的位置等于要求的第k小的数，划分结束
        return;
    } else if (k < num) {
        //当划分的位置大于要求的第k小的数，应更新有区间端点r = pos-1
        selected(input, l, pos - 1, k);
    } else {
         //当划分的位置小于要求的第k小的数，应更新有区间端点l = pos-1
        selected(input, pos + 1, r, k - num);
    }
}

vector<int>  GetLeastNumbers_Solution(vector<int>& input, int k) {
    if(k==0||k>input.size()){
        return  {};
    }
    selected(input, 0, (int)input.size() - 1, k);
    vector<int> ret;
    return vector<int>(input.begin(),input.begin()+k);
}

时间复杂度： $O(n)$ ，这里我们每次递归的时候，区间是没有重合的。我们扫过的区间长度为n。

空间复杂度： $O(n)$ 。最坏情况递归深度为n。每一层需额外空间 $O(1)$ 。总共 $O(n)$ 。