leetcode
leetcode 2851 ~ 2900
最小K个数

最小K个数

难度:

标签:

题目描述

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))

代码结果

运行时间: 35 ms, 内存: 21.1 MB

/*
 * 思路：
 * 1. 使用Java Stream进行排序。
 * 2. 然后通过限制流的大小来获取前k个最小的元素。
 */
import java.util.Arrays;
import java.util.stream.Collectors;

public class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        return Arrays.stream(arr) // 将数组转化为流
                     .sorted()    // 对流进行排序
                     .limit(k)    // 限制流的大小为k
                     .toArray();  // 将流转化为数组
    }
}

解释

方法:

本题解采用了快速选择算法来找到数组中最小的k个数。快速选择是快速排序算法的变形，主要用于在未完全排序的数组中找到第k小的元素。算法首先选择一个随机的枢轴元素，然后将数组分为小于枢轴和大于枢轴的两部分，类似于快速排序。根据枢轴的位置与k的关系，决定是继续在左侧还是右侧递归查找。如果枢轴位置正好是k，那么左侧的元素就是所需的最小的k个数。

时间复杂度:

O(n)

空间复杂度:

O(log n)

代码细节讲解

🦆
为什么在算法中使用随机选取枢轴而不是选择固定位置的元素作为枢轴？
▷
使用随机选取枢轴的主要目的是为了避免在最坏的情况下算法的性能退化。在一些极端情况下，如果总是选择固定位置的元素作为枢轴，例如总是选择第一个或最后一个元素，那么对于已经排序好的数组或者有大量重复元素的数组，快速选择算法会退化成线性时间复杂度，效率大大降低。通过随机选择枢轴，可以在平均情况下保证算法的效率更加稳定。
🦆
在`partition`函数中，当`nums[le]`和`nums[ge]`交换后，为什么仍然需要移动`le`和`ge`的指针？
▷
在`partition`函数中，交换`nums[le]`和`nums[ge]`后，需要移动`le`和`ge`的指针以继续检查后续元素，确保所有小于枢轴的元素都在枢轴的左侧，而大于枢轴的元素都在枢轴的右侧。此外，移动指针也是为了防止重复比较已经交换过的元素，从而避免陷入无限循环，确保每次循环都能进展向前，直到两个指针相遇，结束循环。
🦆
在`random_select`函数中，如果`k`正好等于`nums`，即枢轴的位置，为什么不需要继续递归？
▷
在`random_select`函数中，如果`k`正好等于`nums`，即枢轴的位置，表明枢轴左侧的所有元素加上枢轴本身正好是所需的最小的k个数。此时，枢轴左侧的所有元素都已经是小于等于枢轴的值，不需要进一步排序或选择，因此可以直接返回结果，无需再递归进一步处理。这样做可以提高算法的效率，避免不必要的计算。

相关问题

恢复空格最长单词