341,前 K 個高頻元素

給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

答案：

1public List<Integer> topKFrequent(int[] nums, int k) {
2    List<Integer>[] bucket = new List[nums.length + 1];
3    Map<Integer, Integer> frequencyMap = new HashMap<>();
4    for (int n : nums) {
5        frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
6    }
7    for (int key : frequencyMap.keySet()) {
8        int frequency = frequencyMap.get(key);
9        if (bucket[frequency] == null) {
10            bucket[frequency] = new ArrayList<>();
11        }
12        bucket[frequency].add(key);
13    }
14    List<Integer> res = new ArrayList<>();
15    for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; pos--) {
16        if (bucket[pos] != null) {
17            res.addAll(bucket[pos]);
18        }
19    }
20    return res;
21}

解析：

frepuencyMap中的key是數組中元素，value是數組中元素的個數。代碼比較簡單，很容易理解，但由於題目沒有說清楚，導致算法可能有些不嚴謹，比如數組【1,1,2,2,3】，我們如果求前2高的元素，結果為【1,2】，但如果是求前1高的元素，那麼就會有兩種選擇，要麼是1，要麼是2，當上面解法會把1,2都包含，假如我們只要1，或者2種的一個，我們就要這樣寫

1public List<Integer> topKFrequent(int[] nums, int k) {
2    List<Integer>[] bucket = new List[nums.length + 1];
3    Map<Integer, Integer> frequencyMap = new HashMap<>();
4    for (int n : nums) {
5        frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
6    }
7    for (int key : frequencyMap.keySet()) {
8        int frequency = frequencyMap.get(key);
9        if (bucket[frequency] == null) {
10            bucket[frequency] = new ArrayList<>();
11        }
12        bucket[frequency].add(key);
13    }
14    List<Integer> res = new ArrayList<>();
15    for (int pos = bucket.length - 1; pos >= 0; pos--) {
16        if (bucket[pos] != null) {
17            for (int i = 0; i < bucket[pos].size() && res.size() < k; i++)
18                res.add(bucket[pos].get(i));
19        }
20    }
21    return res;
22}

把上面15-19行的代碼換成下面15-20行的代碼即可。