剑指 Offer 40. 最小的k个数

原题链接

题目描述：

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

一、排序

最直接的思路是排序，升序排列再取前k个即可

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k, 0);
        sort(arr.begin(), arr.end());
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }
};

此时

时间复杂度：O(nlogn)，其中 n 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。

但这肯定不是我们想要的答案，只需要求前k个，却将全部元素置为有序，必然做了无用功。

二、快速划分

其实答案也很简单，霍尔爵士发明的快速划分十分符合本题的要求。

快速划分构造的轴点mi满足：对于任意向量区间 S[lo, hi]。对于任何 lo <= mi < hi，以元素S[mi]为界，分割出的前后两个子向量 S[lo, mi) 和 S(mid, hi)，S[lo, mi) 中的元素均不大于S[mi]，且S(mi, hi)中的元素均不小于S[mi]。

快速排序就是采用分治策略，递归的利用以上轴点的特性，便可实现整体排序。

此时时间复杂度期望为 O(n)，

最坏情况下的时间复杂度为 O(n^2)。

均匀划分时复杂度大体如式：O(N) + O(N / 2) +... = O(N)。具体证明可以参考《算法导论》第 9 章第 2 小节。

我的代码：

class Solution {
public:
    void partition(vector<int>& arr, int l, int r, int k){
        int p = arr[l], i = l, j = r;
        while(l < r){
            while(l < r && p <= arr[r])   r--;
            arr[l] = arr[r];
            while(l < r && p >= arr[l])   l++;
            arr[r] = arr[l];
        }
        arr[l] = p;
        if(l == k - 1)  return ;
        if(l > k - 1)   partition(arr, i, l, k);
        else    partition(arr, l + 1, j, k);
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(arr.size() == 0)
            return vector<int>{};
        if(k == 0)
            return vector<int>{};
        partition(arr, 0, arr.size() - 1, k);
        return vector<int> (arr.begin(), arr.begin() + k);
    }
};

其实中间还挺不顺，平时写快排都是这样写的：

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

y总的模板很好写，也很好理解，但并不满足构造轴点的性质。

又去翻了翻教材霍尔爵士的（quick partitioning），基础算法还是得扎实了哈哈。