最小的K个数（剑指offer-29）

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

题目解析

大小为 K 的最小堆

复杂度：O(NlogK) + O(K)，特别适合处理海量数据。

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

维护一个大小为 K 的最小堆过程如下：在添加一个元素之后，如果大顶堆的大小大于 K，那么需要将大顶堆的堆顶元素去除。

题目解答

import java.util.*;

public class A03 {

        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

            if (k > input.length || k <= 0)

                return new ArrayList<>();

            //lambda表达式，Comparator比较器，相当于一个可以自动排序的队列。

            //PriorityQueue默认是一个小顶堆，然而可以通过传入自定义的Comparator函数来实现大顶堆。

            PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);

            for (int num : input) {

                maxHeap.add(num);

                if (maxHeap.size() > k)

                    maxHeap.poll();

            }

            return new ArrayList<>(maxHeap);

        }

}

巴特西

最小的K个数（剑指offer-29）

题目描述

题目解析

题目解答

最新文章

热门文章