# 前 K 个高频元素

## 题目

• 示例 1:
输入: nums = [1,1,1,2,2,3], k = 2


• 示例 2:
输入: nums = [1], k = 1


• 提示：

## 思路1-列表排序

public static int[] topKFrequent(int[] nums, int k) {
// 参数校验
if(nums == null || k <= 0) {
return null;
}
// 次数统计
Map<Integer, Integer> countMap = new HashMap<>(nums.length);
for(int num : nums) {
int count = countMap.getOrDefault(num, 0) + 1;
countMap.put(num, count);
}

// 计算 topK 的次数
List<Integer> countList = new ArrayList<>(countMap.values());
countList.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// 倒排，次数多的放在前面
return o2 - o1;
}
});

// 1 2 3  TOP3 就是对应最后一个
int countLimit = countList.get(k - 1);
// 5 4 3 2 1
int[] results = new int[k];
int resultIndex = 0;
for(Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
int num = entry.getKey();
int numCount = entry.getValue();
if(numCount >= countLimit) {
results[resultIndex++]  = num;
}
}
return results;
}


Runtime: 10 ms, faster than 64.94% of Java online submissions for Top K Frequent Elements.
Memory Usage: 41.6 MB, less than 62.33% of Java online submissions for Top K Frequent Elements.


## 思路2-优先级队列排序

public static int[] topKFrequent(int[] nums, int k) {
// 次数统计
Map<Integer, Integer> countMap = new HashMap<>(nums.length);
for(int num : nums) {
int count = countMap.getOrDefault(num, 0) + 1;
countMap.put(num, count);
}
// 计算 topK 的次数
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(countMap.values());
int minCount = 0;
int times = priorityQueue.size() - k;
for(int i = 0; i < times; i++) {
minCount = priorityQueue.poll();
}
// 构建结果
int[] results = new int[k];
int resultIndex = 0;
for(Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
int num = entry.getKey();
int numCount = entry.getValue();
if(numCount > minCount) {
results[resultIndex++]  = num;
}
}
return results;
}


Runtime: 9 ms, faster than 84.95% of Java online submissions for Top K Frequent Elements.
Memory Usage: 42.2 MB, less than 18.01% of Java online submissions for Top K Frequent Elements.


## 思路3-TreeMap 实现

TreeMap 也可以达到类似的排序效果：

public static int[] topKFrequent(int[] nums, int k) {
// 次数统计
Map<Integer, Integer> countMap = new HashMap<>(nums.length);
for(int num : nums) {
int count = countMap.getOrDefault(num, 0) + 1;
countMap.put(num, count);
}
TreeMap<Integer, List<Integer>> sortedMap = new TreeMap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// 次數的在前面
return o2 - o1;
}
});

// 设置次数（因为结果唯一，实际上次数并不唯一，可能相同。比如 [1,2]，返回2）
// 如果次数相同，会导致覆盖。
for(Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
// 次数 - 元素
int times = entry.getValue();
List<Integer> list = sortedMap.getOrDefault(times, new ArrayList<>());
sortedMap.put(entry.getValue(), list);
}
// 返回前 k 个
int[] results = new int[k];
int index = 0;
for(Map.Entry<Integer, List<Integer>> entry : sortedMap.entrySet()) {
for(Integer integer : entry.getValue()) {
if(index >= k) {
break;
}
results[index++] = integer;
}
}
return results;
}


Runtime: 9 ms, faster than 84.95% of Java online submissions for Top K Frequent Elements.
Memory Usage: 41.5 MB, less than 62.33% of Java online submissions for Top K Frequent Elements.


# 692. 前K个高频单词

## 题目

• 示例 1：
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2

注意，按字母顺序 "i" 在 "love" 之前。


- 示例 2：





## 思路分析

## 思路1-TreeMap

java
public static List<String> topKFrequent(String[] words, int k) {
// 防御
// 列表为空？内容为空？k 大于 words 长度？
// 次数统计
Map<String, Integer> countMap = new HashMap<>();
for(String string : words) {
countMap.put(string, countMap.getOrDefault(string, 0) + 1);
}

// 次数排序
TreeMap<Integer, List<String>> treeMap = new TreeMap<>((o1, o2) -> o2-o1);
for(Map.Entry<String, Integer> entry : countMap.entrySet()) {
int count = entry.getValue();
List<String> list = treeMap.getOrDefault(count, new ArrayList<>());
treeMap.put(count, list);
}

// 返回结果
List<String> results = new ArrayList<>(k);
for(List<String> values : treeMap.values()) {
// 排序
Collections.sort(values);
// 添加元素
for(String value : values) {
if(results.size() >= k) {
return results;
}
}
}
return results;
}


Runtime: 7 ms, faster than 23.26% of Java online submissions for Top K Frequent Words.
Memory Usage: 39.3 MB, less than 36.81% of Java online submissions for Top K Frequent Words.


## 思路2-排序

public static List<String> topKFrequent(String[] words, int k) {
// 次数统计
Map<String, Integer> countMap = new HashMap<>(words.length);
for(String string : words) {
countMap.put(string, countMap.getOrDefault(string, 0) + 1);
}

// 次数排序
List<String> sortList = new ArrayList<>(countMap.keySet());
sortList.sort(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
//1. 比较次数
int count1 = countMap.get(o1);
int count2 = countMap.get(o2);
// 次数不等
if (count1 != count2) {
return count2 - count1;
} else {
// 自然排序
return o1.compareTo(o2);
}
}
});

// 截取结果
return sortList.subList(0, k);
}


### 效果

Runtime: 5 ms, faster than 86.38% of Java online submissions for Top K Frequent Words.
Memory Usage: 39.3 MB, less than 36.81% of Java online submissions for Top K Frequent Words.


### 辅助度

ps: 实际上可以发现 Leetcode 中的很多题目，解法是大同小异的。

# 215. 数组中的第K个最大元素

## 题目

• 示例 1:
输入: [3,2,1,5,6,4] 和 k = 2


• 示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4



## 思路1-排序

### 效果

public static int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}


### 效果

Runtime: 1 ms, faster than 98.08% of Java online submissions for Kth Largest Element in an Array.
Memory Usage: 39.2 MB, less than 60.04% of Java online submissions for Kth Largest Element in an Array.


## 思路2-堆

public static int findKthLargest(int[] nums, int k) {
int len = nums.length;
// 使用一个含有 len 个元素的最大堆，lambda 表达式应写成：(a, b) -> b - a
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, (a, b) -> b - a);
for (int num : nums) {
}
for (int i = 0; i < k - 1; i++) {
maxHeap.poll();
}
return maxHeap.peek();
}


Runtime: 4 ms, faster than 62.52% of Java online submissions for Kth Largest Element in an Array.
Memory Usage: 39.2 MB, less than 60.04% of Java online submissions for Kth Largest Element in an Array.


# 参考资料

https://leetcode-cn.com/problems/number-of-digit-one/