map + 自定义list排序规则 — 自己的思路
时间复杂度: $OO(n + m + m * log m + k)$ — map添加n个元素 + m个不同元素变为list + 快排 + 取k个
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i ++) map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, (o1, o2) -> Integer.compare(o2.getValue(), o1.getValue()));
int[] rs = new int[k];
for(int i = 0; i < k; i ++) rs[i] = list.get(i).getKey();
return rs;
}
}
map统计元素出现个数 + 计数数组,用于统计出现k次的数的分界点在哪里 + 通过分界点遍历 map 找到所有出现次数大于等于i的数,所以时间复杂度是$O(n)$
如图所示:
代码如下
class Solution {
public int[] topKFrequent(int[] nums, int m) {
int n = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < n; i ++) map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
int[] sum = new int[n + 1];
for(Integer i : map.values()) sum[i] ++;
int k = m;
for(int i = n; i >= 0; i --) {
k -= sum[i];
if(k <= 0) {
k = i;
break;
}
}
int[] rs = new int[m];
int p = 0;
for(Integer i : map.keySet()) {
if(map.get(i) >= k) rs[p ++ ] = i;
}
return rs;
}
}