⭐ 题目日期：

阿里-2024/12/28, 美团 - 2024/10/16

🌳 题目示例：

例如：
- 输入：1 -> 2 -> 3 -> 4 -> 5, K = 2
- 输出：4 -> 5 -> 1 -> 2 -> 3

🧗难度系数：

⭐️ ⭐️ ⭐ ⭐

📝解题思路：

不难想到将数组排序，取前K个数，时间复杂度：O(nlogn)。排序方法的问题在于在我们不在乎大于K的数的顺序的情况下，仍然将这部分数排序了，导致无谓的消耗，时间复杂度过高。

💻 解法 一：堆

堆刚好能帮我们维护 k 个最小的数，将剩下的 n - k 个数隔离。

使用大顶堆（优先队列）：

• 维护一个容量为 k 的大顶堆（Java 中的 PriorityQueue 默认是小顶堆）。
• 遍历数组，将元素加入堆中。
  • 如果堆里的元素个数小于 k，直接加入堆。
  • 如果堆里的元素个数大于等于 k，且当前元素小于堆顶元素（堆中所有元素的最大值），则弹出堆顶元素，将当前元素加入堆。
• 最终，堆中保存的就是最小的 k 个数。

Java

public int[] getKMinElements(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k <= 0) {
        return null;
    }
    if (k >= nums.length) {
        return nums;
    }

    // 使用大顶堆，容量为 k
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (a, b) -> b - a);

    // 遍历数组
    for (int num : nums) {
        if (maxHeap.size() < k) {
            maxHeap.offer(num); 
        } else if (num < maxHeap.peek()) {
            maxHeap.poll();     
            maxHeap.offer(num); 
        }
    }

    // 将堆中的元素取出，存入结果数组
    int[] result = new int[k];
    int index = k - 1;
    while (!maxHeap.isEmpty()) {
        result[index--] = maxHeap.poll();
    }

    return result;
}

复杂度分析

时间复杂度：O(n log k)，其中 n 是数组长度。

建堆：O(k), 至多 n - k 个元素进行堆的删除, 插入, 堆调整, O(n - k)logk

总的时间复杂度：O(k) + O(n - k)logk < O(nlogk)

空间复杂度：O(k), 堆的容量为k, 以及额外存储空间数组的长度也为k, 总的空间为O(2k) = O(k)

🚵🏻解法 二：快速选择(Quick Select)

思路分析：快速选择算法是一种用于在未排序列表中查找第 k 小元素的选择算法。它与快速排序（Quicksort）算法相关联。

从数组中选择前 k 个最小元素（即索引从 0 到 k−1 的元素），可以使用快速选择算法第 k 小的元素对数组进行划分。

！！！详细过程及复杂度分析，请查阅快速排序

public int[] getKMinElements(int[] array, int k) {
    if (array == null || array.length == 0 || k <= 0) {
        return null;
    }
    if (k >= array.length) {
        return array;
    }
    // 索引从 0 开始，我们需要找 0, ... k - 1, 故传参 k - 1
    quickSelectK(array, 0, array.length - 1, k - 1);
    return Arrays.copyOfRange(array, 0, k);
}

private void quickSelectK(int[] array, int left, int right, int k) {
    if (left >= right) {
        return;
    }
    int pivotIndex = partition(array, left, right);
    if (pivotIndex == k) {
        return;
    } else if (pivotIndex < k) {
        quickSelectK(array, pivotIndex + 1, right, k);
    } else {
        quickSelectK(array, left, pivotIndex - 1, k);
    }
}

private int partition(int[] array, int left, int right) {
    int i = left;
    int j = right - 1;
    while (i <= j) {
        if (array[i] <= array[right]) {
            i++;
        } else {
            swap(array, i, j);
            j--;
        }
    }
    swap(array, i, right);
    return i;
}

private void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

复杂度分析

时间复杂度：

1. 平均时间复杂度：O(n), 平均每次将数组减半，搜索一半，抛弃一半，n/2 + n/4 + n/8 + ... + 1 = O(n)

2. 最坏情况：O(n^2), 基准选择太不巧了，每次只能淘汰一个元素，n + (n - 1) + (n - 2) + ... + 1 = O(n^2)

空间复杂度：

1. 平均：O(logn), 递归栈的调用深度，每次减半，最大深度 logn

2. 最坏：O(n), 递归栈的调用深度，基准选择太不巧了，每次只能淘汰一个元素，最大的深度 n