首页 > 代码库 > LeetCode Top K Frequent Elements

LeetCode Top K Frequent Elements

2024-09-02 20:30:24   208人阅读

原题链接在这里：https://leetcode.com/problems/top-k-frequent-elements/

题目：

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: 

    • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
    • Your algorithm‘s time complexity must be better than O(n log n), where n is the array‘s size.

题解：

可以使用bucket. 把nums array按照元素出现频率放在bucket中. 最大频率是nums.length, 所以bucket的大小是nums.length+1, 才能对应最大频率.

然后从bucket后扫到前，把nums元素加到res中.

Note: bucket的生成等号右边是ArrayList[] 而不能是ArrayList<Integer>[], 因为complier 不能判准加进ArrayList中的tepe, 只有run time才能知道. 所以这里complier不允许确定type.

Time Complexity: O(n), n = nums.length.

Space: O(n).

AC Java:

 1 public class Solution {
 2     public List<Integer> topKFrequent(int[] nums, int k) {
 3         List<Integer> res = new ArrayList<Integer>();
 4         if(nums == null || nums.length == 0 || k < 1){
 5             return res;
 6         }
 7         
 8         HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
 9         for(int num: nums){
10             hm.put(num, hm.getOrDefault(num, 0)+1);
11         }
12         
13         ArrayList<Integer> [] bucket = new ArrayList[nums.length+1];
14         for(int key : hm.keySet()){
15             int freq = hm.get(key);
16             if(bucket[freq] == null){
17                 bucket[freq] = new ArrayList<Integer>();
18             }
19             bucket[freq].add(key);
20         }
21         
22         for(int i = bucket.length-1; i>=0 && res.size()<k ; i--){
23             if(bucket[i] != null){
24                 res.addAll(bucket[i]);
25             }
26         }
27         return res;
28     }
29 }

类似Sort Characters By Frequency.

LeetCode Top K Frequent Elements


联系
我们