提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

最小的 K 个数

数组
2023-04-18 12:56:57 时间

题目描述

描述 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。 数据范围：0≤k,n≤10000，数组中每个数的大小0 ≤val≤1000 要求：空间复杂度 O(n) ，时间复杂度 O(nlogn)

输入：

[4,5,1,6,2,7,3,8],4 
返回值：
[1,2,3,4]

说明： 返回最小的4个数即可，返回[1,3,2,4]也可以

解题思路

大小为 K 的最小堆

  • 时间复杂度：O(NlogK)
  • 空间复杂度：O(K)
  • 特别适合处理海量数据 维护一个大小为 K 的最小堆过程如下：使用大顶堆。在添加一个元素之后，如果大顶堆的大小大于 K，那么将大顶堆的堆顶元素去除，也就是将当前堆中值最大的元素去除，从而使得留在堆中的元素都比被去除的元素来得小。

应该使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。

Java 的 PriorityQueue 实现了堆的能力，PriorityQueue 默认是小顶堆，可以在在初始化时使用 Lambda 表达式 (o1, o2) -> o2 - o1 来实现大顶堆。其它语言也有类似的堆数据结构。

public class Topk {
    public static void main(String[] args) {
        int[] nums = {4,5,1,6,2,7,3,8};
        List<Integer> leastNumber = new Topk().getLeastNumber(nums, 4);
        System.out.println(leastNumber);
    }
    public List<Integer> getLeastNumber(int[] nums, int k) {
        if (k > nums.length || k <= 0)
            return new ArrayList<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int num : nums) {
            maxHeap.add(num);
            if (maxHeap.size() > k)
                maxHeap.poll();
        }
        return new ArrayList<>(maxHeap);
    }

}

相关文章