面试题 17.14. Smallest K LCCI

力扣原题
Design an algorithm to find the smallest K numbers in an array.

Example:

Input: arr = [1,3,5,7,2,4,6,8], k = 4
Output: [1,2,3,4]

Note:

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

分析

典型的前K个最大，最小值问题；

用堆

来算一下时间复杂度，建堆 $O(n)$，出堆 $O(logn)$ ，一共出堆 $k$ 次。
总的时间复杂度是： $$O(n+klogn)$$
空间复杂度（建堆）是：
$$O(n)$$
能不能直接降到$O(n)$啊？

快排思想

每一次快排之后的基准(哨兵) $pivot$ 的下标为 $index$，则左边都是比它小的，一共有$index$个，右边都是比它大的。

1. 如果 $index=k$ 则左边的元素我们所求的“前k个最小”。
2. 如果 $index>k$ 则继续对基准左边快排: fast_sort(arr, k, start, left - 1)
3. 如果 $index<k$ 则继续对基准右边快排: fast_sort(arr, k, ledt + 1, end)

快排思想代码

class Solution {
public:
    vector<int> ans;
    void fast_sort(vector<int> &arr, int k, int start, int end) {
        int left = start, right = end;
        while (left < right) {
      		// 如果标记在右边， 那第一个 while 就先从左到右
      		// 否则从右到左
            while (left < right && arr[left] <= arr[end]) left++;
            while (left < right && arr[right] >= arr[end]) right--;    
            swap(arr[left], arr[right]);
        }
        swap(arr[left], arr[end]);
        if (left < k) fast_sort(arr, k, left + 1, end);
        if (left > k) fast_sort(arr, k, start, left - 1);
        ans.assign(arr.begin(), arr.begin() + k);
    }
    vector<int> smallestK(vector<int>& arr, int k) {
    	// 如果有的题目 k > n 就做下面这个判断 
        // if (k >= arr.size()) return arr;
        
        fast_sort(arr, k, 0, arr.size() - 1);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

就是加了两个判断。