剑指 Offer 40: 最小的k个数

[songyy5517]

输入整数数组 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个数。一个很直接的想法是对数组先排序，再按顺序取出最小的k个数。但这种方法的时间复杂度取决于具体的排序算法。考虑到快速排序的性质，每次选取一个基准元素pivot，可以将整个数组分成两个部分，其左边的元素都小于基准元素，右边的元素都大于基准元素。因此，我们无需对整个数组进行排序，只需找到索引为k - 1的基准元素即可，从而降低了时间复杂度。

[songyy5517]

思路1：基于快速排序的数组排列

1. 异常处理；
2. 定义递归快排方法（quickSort），对数字进行快排，获取基准元素的下标 $index$ ，直到找到下标为 $k-1$ 的基准元素。 （1）若基准元素的下标等于 $k-1$ ，则停止划分； （2）若大于 $k-1$ ，则对区间 $[start, index-1]$ 进行相同的快排划分操作； （3）若小于 $k-1$ ，则对区间 $[index+1, end]$ 进行相同的快排划分操作；
3. 定义快排划分方法（partition）：在数组中选取一个元素（区间首元素），并对数组进行排列，保证其左边的元素均小于该元素，右边的元素均大于该元素 （1）定义相关变量：基准元素 $criterion$ （当前区间的首元素），向后指针 $left$ , 向前指针 $right$ （分别按照从前向后/从后向前的方向遍历数组） （2）当两指针未相遇时 $(left <= right)$ ，进行以下操作：
   • 通过向后指针 $left$ ，找到第一个大于基准元素的元素；
   • 通过向前指针 $right$ ，找到第一个大于基准元素的元素；
   • 若两指针没有重合，则交换两元素的位置； （3）将基准元素于两指针相遇位置 $(right)$ 的元素互换位置； （4）返回基准元素的下标 $(right)$ 。
4. 返回数组前 $k$ 个元素。

复杂度分析：

• 时间复杂度： $O(N)$，其中 $N$ 为数组元素数量；对于长度为 $N$ 的数组执行一次哨兵划分操作的时间复杂度为 $O(N)$ ；每轮哨兵划分后根据 k 和 i 的大小关系选择递归，由于 i 分布的随机性，则向下递归子数组的平均长度为 $\frac{N}{2}$ ；因此平均情况下，哨兵划分操作中的扫描次数一共为 $N + \frac{N}{2} + \frac{N}{4} + ... + \frac{N}{N} = \frac{N - \frac{1}{2}}{1 - \frac{1}{2}} = 2N - 1$ （等比数列求和: $S_n = \frac{a_1 - a_n * q}{1 - q}$ ），即总体时间复杂度为 $O(N)$ . 相较于标准的快速排序，此算法省去了不必要的递归partition操作（剪枝，去掉了不包含索引为k - 1元素的一半），因此时间复杂度由 $O(N\log N)$ 降到了 $O(N)$ 。

最坏情况下的时间复杂度也为 $O(N)$ ：情况最差时，每次的划分点都是最大值或最小值，一共需要划分 $k$ 次，而一次划分需要线性的时间复杂度，所以最坏情况下时间复杂度为 $O(N)$。 $(n-1) + (n-2) + ...+ (n-k)$

LCR 159. 库存管理 III（快速选择，清晰图解）

• 空间复杂度： $O(logN)$，划分函数递归的平均深度为 $O(logN)$。

[songyy5517]

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型一维数组 
     * @param k int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        // Approach: Sort & Pick
        // 1. Exceptions
        ArrayList<Integer> res = new ArrayList();

        if (input == null || input.length == 0 || k == 0)
            return res;
        if (k > input.length)
            k = input.length;

        // 2. Sort
        quickSort(input, 0, input.length - 1, k);

        for(int i = 0; i < k; i++)
            res.add(input[i]);

        return res;
    }

    // 以start为基准元素，对范围[i,j]的元素快速排序，直到基准元素的下标等于k-1
    // 这里必须递归，不然首尾边界永远不会变
    void quickSort(int[] input, int start, int end, int k){
        int index = partition(input, start, end);
        if (index == k-1)
            return ;

        if (index < k - 1){
            quickSort(input, index+1, end, k);
        }
        else{
            quickSort(input, start, index-1, k);
        }

        return;
    }

    // 快排的partition操作
    int partition(int[] input, int start, int end){
        int criterion = input[start];
        int left = start + 1, right = end;

        while (left <= right){
            while (left <= right && input[left] <= criterion) left++; 
            while (right >= left && input[right] >= criterion) right--;  
            if (left >= right)
                break;

            int temp = input[left];
            input[left] = input[right];
            input[right] = temp;
        }

        // 将基准元素放置其对应的位置
        input[start] = input[right];
        input[right] = criterion;

        return right;
    }
}

[songyy5517]

思路2：基于堆排序的数组排列

1. 异常处理；
2. 构建一个大小为 $k$ 的最大堆；
3. 遍历整个数组： （1）将数组中前 $k$ 个元素依次加入最大堆中； （2）之后的元素依次与最大堆的堆顶元素进行比较，若当前遍历的元素小于最大堆堆顶元素，则将最大堆堆顶元素替换成当前元素；
4. 返回最大堆中的所有元素。

复杂度分析

• 时间复杂度： $O(Nlog_2k)$ ，我们需要遍历数组中的 $N$ 个元素，并对每个元素进行 $log_2k$ 次比较；
• 空间复杂度： $O(k)$ ，最大堆中始终有 $k$ 个元素。

[songyy5517]

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型一维数组 
     * @param k int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        // write code here
        // Approach: Heap Sort
        // 1. Exceptions
        ArrayList<Integer> res = new ArrayList();

        if (input == null || input.length == 0 || k == 0)
            return res;
        if (k > input.length)
            k = input.length;

        // 2. Define Max Heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((x, y)->(y - x));
        for(int i = 0; i < input.length; i++){
            if (i < k){
                maxHeap.add(input[i]);
                continue;
            }

            if (input[i] < maxHeap.peek()){
                maxHeap.remove();
                maxHeap.add(input[i]);
            }

        }

        while (!maxHeap.isEmpty())
            res.add(maxHeap.remove());

        return res;
    }
}

[songyy5517]

2023/2/8

1. 用双指针实现patition方法，一开始不需要将基准元素放置数组末尾

2023/11/14

1. 基于快排 & 基于堆排序

2024/2/28

1. 最大堆的定义。

2024/3/5

1. 快排代码：移动前后指针的while循环条件 while (left <= right && ....)
2. 快速排序解法的时间空间复杂度

2024/3/22