import java.util.*;

public class Solution347 {

/**

* 找出高频的前n个数

* 1. 小根堆

*

* @param nums 数组

* @param k 数值

* @return 结果

*/

public int[] topKFrequent(int[] nums, int k) {

if (k == 0) return new int[0];

Map<Integer, Integer> map = new HashMap<>(nums.length);

for (int num: nums) {

map.put(num, map.containsKey(num) ? map.get(num) + 1 : 1);

}

PriorityQueue<int[]> heap = new PriorityQueue<>((a1, a2) -> a1[1] - a2[1]);

for (Map.Entry<Integer, Integer> entry: map.entrySet()) {

heap.offer(new int[] {entry.getKey(), entry.getValue()});

if (heap.size() > k) {

heap.poll();

}

}

int[] result = new int[k];

for (int i = 0; i < k; i++) {

result[i] = heap.poll()[0];

}

return result;

}

/**

* 找出高频的前n个数

* 2. 桶排序

*

* @param nums 数组

* @param k 数值

* @return 结果

*/

public int[] topKFrequent2(int[] nums, int k) {

if (k == 0) return new int[0];

Map<Integer, Integer> map = new HashMap<>(nums.length);

for (int num: nums) {

map.put(num, map.containsKey(num) ? map.get(num) + 1 : 1);

}

// 因为频率最大可以等于长度，所以此处要+1

List<Integer>[] list = new List[nums.length + 1];

for (int key: map.keySet()) {

int i = map.get(key);

if (list[i] == null) {

list[i] = new ArrayList<>();

}

list[i].add(key);

}

int[] result = new int[k];

int index = 0;

for (int i = list.length - 1; i >= 0 && index < k; i--) {

if (list[i] == null) {

continue;

}

for (Integer num: list[i]) {

result[index++] = num;

}

}

return result;

}

public static void main(String[] args) {

System.out.println(new Solution347().topKFrequent2(new int[] {1,1,1,2,2,3}, 2));

}

}