NC119 最小(或最大)的K个数 （java 大根堆小根堆思路）_求最大的k个数java

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

示例1
输入：
[4,5,1,6,2,7,3,8],4
返回值：
[1,2,3,4]
说明：
返回最小的4个数即可，返回[1,3,2,4]也可以

示例2
输入：
[1],0
返回值：
[]

示例3
输入：
[0,1,2,1,2],3
返回值：
[0,1,1]

思路：
1、new一个大根堆，维护其大小为k。
2、最开始一直往里面加数据，直到k的大小
3、然后每次看一下大根堆里面的第一个数（堆顶），如果数组的数比它小，就把它换进去。（就是先删后加）,这样每次都能保证最小的只有k个。
4、最后需要把堆里的数据搬到list上。

空间复杂度 O(k) ，时间复杂度 O(n*longk)
为什么需要乘以logk呢，因为每次维持最大值需要logk的时间

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class MinK {
    public static void main(String[] args) {
        int[] input = {3, 4, 6, 6, 8, 98, 6, 5, 4, 2, 1};
        GetLeastNumbers_Solution(input, 4);
        GetLargestNumbers_Solution(input,5);


    }
    //求最小的k个数
    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (k == 0 || k > input.length) return list;

        //大根堆需要 重写比较器
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int val : input) {
            if (queue.size() < k) {
                queue.add(val);
            } else {
                if (val < queue.peek()) {
                    queue.poll();
                    queue.add(val);
                }
            }
        }
        while (!queue.isEmpty()) {
            list.add(queue.poll());
        }

        return list;

    }
    //求最大的k个数
    public static ArrayList<Integer> GetLargestNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (k == 0 || k > input.length) return list;

        //小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int val : input) {
            if (queue.size() < k) {
                queue.add(val);
            } else {
                if (val > queue.peek()) {
                    queue.poll();
                    queue.add(val);
                }
            }
        }
        while (!queue.isEmpty()) {
            list.add(queue.poll());
        }
        return list;

    }

}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70