Java O(n) solution using buckets. Beats 95%.


  • 0
    M
    public List<Integer> topKFrequent(int[] nums, int k) {
            List<Integer> result = new ArrayList<>();
            List<Integer>[] bucket = new List[nums.length+1];
            
            Map<Integer, Integer> map = new HashMap<>();
            for(int i=0; i<nums.length; i++){
                int val = map.getOrDefault(nums[i],0) + 1;
                map.put(nums[i], val);
            }
            for(Integer key: map.keySet()){
                int frequency = map.get(key);
                if(bucket[frequency] == null){
                    bucket[frequency] = new ArrayList<>();
                }
                bucket[frequency].add(key);
            }
            for(int i=bucket.length-1; i>=0 && result.size()<k; i--){
                if(bucket[i]!=null){
                    List<Integer> list = bucket[i];
                    for(Integer n: list){
                        result.add(n);
                        if(result.size()==k){
                            break;
                        }
                    }
                }
            }
            return result;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.