[LeetCode] 347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:
Input: nums = [1], k = 1
Output: [1]

Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

前 K 个高频元素。

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

思路

前 K 个 XX 的题型思路大多不是 pq 就是 bucket sort。题目要求时间复杂度必须优于 O(nlogn)。
因为题目有时间复杂度的要求所以只能是 bucket sort 桶排序的思想做。

解释一下思路，既然是桶排序，所以需要将出现频率一样的元素放到同一个桶里面，所以这里会用到一个 hashmap 记录数字和他们各自出现频率（key:value）。接着就需要根据频率大小，挑出前 K 个频率最大的元素。

复杂度

时间O(n) - 题目要求
空间O(n)

代码

Java实现

class Solution {
	public int[] topKFrequent(int[] nums, int k) {
		// 记录不同元素分别出现的个数
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int num : nums) {
			map.put(num, map.getOrDefault(num, 0) + 1);
		}

		// bucket sort
		List<Integer>[] bucket = new List[nums.length + 1];
		for (int key : map.keySet()) {
			int freq = map.get(key);
			// 把出现次数相同的元素放在同一个桶里
			if (bucket[freq] == null) {
				bucket[freq] = new ArrayList<>();
			}
			bucket[freq].add(key);
		}

		int[] res = new int[k];
		int index = 0;
		// 从出现次数大的桶开始
		for (int i = bucket.length - 1; i >= 0 && index < k; i--) {
			if (bucket[i] != null) {
				for (int num : bucket[i]) {
					res[index++] = num;
					if (index == k) {
						break;
					}
				}
			}
		}
		return res;
	}
}