前 K 个高频元素

秒速五厘米 2024-04-06 12:25 58阅读 0赞

### 347. 前 K 个高频元素 ###

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

##### 示例 1: #####

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

##### 示例 2: #####

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

##### 提示： #####

*   1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
 *  k 的取值范围是 \[1, 数组中不相同的元素的个数\]
 *  题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

#### 分析： ####

首先依旧使用哈希表统计频率，统计完成后，创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标即可。

#### 代码（Java）: ####

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    
    public class topK {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int nums [] = {
        1};
    		int k = 1;
    		int [] l = new int[5];
    		int [] list = topKFrequent(nums, k);
    		for(int num: list) {
        
    			System.out.println(num);
    		}
    	}
    	
    	public static int [] topKFrequent(int[] nums, int k) {
        
    		List<Integer> res = new ArrayList();
    		
    		HashMap<Integer,Integer> map = new HashMap();
    		//使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
    		
    		for(int i=0; i<nums.length; i++) {
        
    			if(map.containsKey(nums[i])) {
        
    				map.put(nums[i], map.get(nums[i]) + 1);
    			}else {
        
    				map.put(nums[i], 1);
    			}
    				
    		}
    		
    		//桶排序
    		//将频率作为数组的下标，对于出现频率不同的数字集合，存入对应的数组下标
    		List<Integer>[] list =  new List[nums.length+1];
    		for(int key: map.keySet()) {
        
    			//将每个元素出现的次数作为数组下标
    			int i = map.get(key);
    			if(list[i] == null) {
        
    				list[i] = new ArrayList();
    			}
    			list[i].add(key);
    		}
    		
    		//倒序遍历数组获取出现从大到小的排列
    		for(int i = list.length - 1; i >= 0 && res.size() < k; i--) {
        
    			if(list[i] == null)
    				continue;
    			res.addAll(list[i]);
    		}
    		
    		int [] l = new int[res.size()];
            int i = 0;
            for(int num : res) {
        
    			l[i++] = num;
    		}
    		return l;
        }
    
    }

#### 复杂度分析: ####

*  时间复杂度：O(n)，n 表示数组的长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；桶的数量为n+1，所以桶排序的时间复杂度为O(n)；因此，总的时间复杂度是 O(n)。
 *  空间复杂度：很明显为O(n)

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

来源：[力扣（LeetCode）][LeetCode]  
注：仅供学习参考！

[LeetCode]: https://leetcode.cn/problems/top-k-frequent-elements