LeetCode 291は、非空の整数配列を与え、頻度が現れる前のkより高い要素を返す.
1433 ワード
非空の整数配列が与えられ、周波数が現れる前にkの高い要素が返される.
例1:
例2:
説明:与えられたkは常に合理的であり、1≦k≦配列中の異なる要素の個数であると仮定することができる. あなたのアルゴリズムの時間的複雑さはO(n log n)より優れなければなりません.nは配列の大きさです.
解法:javaバケツソート実装--serpmelon
例1:
: nums = [1,1,1,2,2,3], k = 2
: [1,2]
例2:
: nums = [1], k = 1
: [1]説明:
解法:javaバケツソート実装--serpmelon
public List topKFrequent(int[] nums, int k) {
HashMap map = new HashMap<>();
for(int i : nums) { // ，key ，value
map.put(i, map.getOrDefault(i, 0) + 1);
}
// nums.length + 1
List[] bucket = new List[nums.length + 1];
// map， value
for(Map.E***y e : map.e***ySet()) {
Integer value = e.getValue();
if(bucket[value] == null) {
bucket[value] = new ArrayList();
}
bucket[value].add(e.getKey());
}
List freList = new ArrayList<>();
// ，
for(int j = bucket.length - 1; j > -1 && freList.size() < k; j--) {
if(bucket[j] != null)
freList.addAll(bucket[j]);
}
return freList;
}