一、题目描述

JZ29 最小的K个数
题目大意：给定一个数组, 找出其中最小的k个数
注意审题：若k大于数组的长度, 就返回空数组

二、算法1（排序）

解题思路

  1. 说到求最小(或最大)的k个数这一类问题, 我们一般是想法就是先对数组进行排序,然后取边缘连续的k个数即可
  2. 要求最小的k个数, 我们可以将数组从小到大排序, 然后取前k个数为答案即可

代码实现 (C++11)

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        int n = input.size();
        if(k > n) return ans;        // 若k大于数组长度, 返回空数组
        sort(input.begin(), input.end());    // 从小到大排序
        ans = vector<int>(input.begin(), input.begin() + k);    // 返回前k个数
        return ans;
    }
};

时间复杂度：O(nlogn), 取决于排序的快慢
空间复杂度：O(1)

三、算法2（堆）

解题思路

  1. 堆(优先队列)这一数据结构可以支持O(logn)的插入和堆顶出队操作, 因此我们可以用一个大小为k的大根堆来维护数组最小的k个数
  2. 算法实现：当堆的大小小于k时, 直接插入即可; 当堆的大小等于k时, 将当前待插入元素与堆顶元素进行比较, 如果小于堆顶元素, 则堆顶出堆, 当前元素入堆, 否则不插入当前元素, 最后堆中就保留了最小的k个数, 我们再将其取出即可

图片说明

代码实现（C++11）

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
        int n = input.size();
        if(k > n) return ans;
        priority_queue<int> max_heap;    // 创建最大堆

        for(int i = 0; i < input.size(); i++){
            if(max_heap.size() < k) max_heap.push(input[i]);    // 堆的大小不足k
            else{
                if(max_heap.size() && input[i] < max_heap.top()){    // 堆若不空, 则把当前元素与堆顶比较
                    max_heap.pop();
                    max_heap.push(input[i]);
                }
            }
        }

        while(max_heap.size()){        // 取出堆中的k个元素
            ans.push_back(max_heap.top());
            max_heap.pop();
        }

        return ans;
    }
};

时间复杂度：O(nlogk), 堆的每次操作时间复杂度不超过O(logk)
空间复杂度：O(k)

四、算法三（快速选择算法）

解题思路

  1. 根据题目可知，返回的数组不必是有序的，故我们可以想到快速选择算法来解决本问题，不熟悉快速选择算法的可以先看看第k个数这题，与其思路一致，我们可以利用快速排序的思想来实现
  2. 快速排序每次根据一个pivot点对区间进行划分，使得pivot左侧的数都比它小，右侧的数都比它大，然后再对两部分就行划分，而快速选择只需要选择其中一部分进行划分即可，根据k可以选择进入那个递归入口，这样的期望时间复杂度是线性的，但最坏情况下是O(n^2)的
  3. 算法步骤，首先选择数组中点为pivot，再使用双指针算法交换左侧大于等于pivot的数和右边小于等于pivot的数，最后我们可以保证数组被分为了以pivot划分的两部分，接着根据k选择递归入口即可，算法结束后我们可以保证数组的前k个数是最小的k个数，但是并不是升序的

代码实现（C++11）

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        quickSelect(input, 0, input.size() - 1, k);
        return vector<int>(input.begin(), input.begin() + k);
    }

    void quickSelect(vector<int>& input, int l, int r, int k){
        if(l >= r) return;
        int i = l - 1, j = r + 1, pivot = input[l + r >> 1];
        // 令小于pivot的数都在左侧, 大于pivot的数都在右侧
        while(i < j){
            while(input[++i] < pivot);
            while(input[--j] > pivot);
            if(i < j) swap(input[i], input[j]);
        }
        int cnt = j - l + 1;    // cnt表示小于等于pivot的数的数量
        if(cnt >= k){    // 若cnt >= k, 说明答案在左区间
            return quickSelect(input, l, j, k);
        }
        return quickSelect(input, j + 1, r, k - cnt);    // 左边cnt个数已经确定, 只要确定右边的即可
    }
};

时间复杂度：期望O(n)，n为数组长度，最坏时间复杂度为O(n^2)
空间复杂度：期望O(logn)，递归调用的期望深度为logn，但最坏情况为O(n)