【LeetCode】- Java - 前K个高频元素

妖狐艹你老母 2022-01-31 14:04 147阅读 0赞

题目描述：给定一个非空的整数数组，返回其中出现频率前 ***k*** 高的元素。

**示例 1:**

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

**示例 2:**

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

**说明：**

*  你可以假设给定的 *k* 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 *  你的算法的时间复杂度**必须**优于 O(*n* log *n*) , *n* 是数组的大小。

解法一：使用优先队列，先获取每个元素出现的次数，然后根据出现次数加到优先队列中，依次出队k次就是需要的解，我的代码如下：

public class TopKFrequent {
    	public List<Integer> topKFrequent(int[] nums, int k) {
    		List<Integer> list = new ArrayList<>();
    
    		// 先定义一个优先队列
    		PriorityQueue<Entry<Integer, Integer>> queue = new PriorityQueue<>(new Comparator<Entry<Integer, Integer>>() {
    			@Override
    			public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
    
    				return o2.getValue() - o1.getValue();
    			}
    		});
    
    		// 获取每个元素出现的次数
    		Map<Integer, Integer> map = new HashMap<>();
    		for (int i = 0; i < nums.length; i++) {
    			map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    		}
    
    		// 加入到队列中
    		for (Entry<Integer, Integer> entry : map.entrySet())
    			queue.add(entry);
    
    		// 出队K次
    		for (int i = 0; i < k; i++)
    			list.add(queue.poll().getKey());
    
    		return list;
    	}
    }

方法二：先用HashMap存放每个元素出现的次数，定义n+1个桶，把出现的次数映射到桶中，使用拉链法解决冲突，倒序遍历桶，当找出的元素的个数等于k时即是需要的结果，如 nums=\{1,1,2,2,3\},k等于2时的图如下

> map 的 结果 ：1-2 ，2-2 ，3-1，定义6个桶，分别标序号为0-5，元素1出现2次，元素2出现2次，元素3出现一次，映射到桶中，如下所示，
> 
> 0  1  2 3   4  5 
> 
> 3 1
> 
> 2
> 
> 倒序遍历桶，res个数大于k时终止，

我的代码如下

public class TopKFrequent {
    	public List<Integer> topKFrequent(int[] nums, int k) {
    
    		// 定义一个桶
    		ArrayList<Integer>[] bucket = new ArrayList[nums.length + 1];
    
    		// 获得每个元素出现的 次数
    		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    		for (int i = 0; i < nums.length; i++) {
    			map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    		}
    
    		for (Integer n : map.keySet()) {
    			Integer value = map.get(n);
    			if (bucket[value] == null) {
    				ArrayList<Integer> list = new ArrayList();
    				bucket[value] = list;
    			}
    			bucket[value].add(n);
    		}
    		List<Integer> res = new ArrayList<>();
    		for (int i = nums.length; i >= 0 && res.size() < k; i--) {
    			if (bucket[i] != null) {
    				res.addAll(bucket[i]);
    			}
    		}
    		return res;
    	}
    }

参考：[https://leetcode-cn.com/problems/top-k-frequent-elements/comments/][https_leetcode-cn.com_problems_top-k-frequent-elements_comments]

[https_leetcode-cn.com_problems_top-k-frequent-elements_comments]: https://leetcode-cn.com/problems/top-k-frequent-elements/comments/