4 ms Java bucket sort solution. Beats 100%


  • 0
    T
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> result = new LinkedList<Integer>();
        if(nums.length==0) return result;
        int min = nums[0], max = nums[0];
        for(int i = 1;i < nums.length; i++){
            if(nums[i]<min) min = nums[i];
            else if(nums[i]>max) max = nums[i];
        }
        int[] map = new int[max-min+1];
        for(int i = 0; i < nums.length; i++) map[nums[i]-min]++;
        List<Integer> [] bucket = new List[nums.length+1];
        for(int integer = 0;integer<max-min+1; integer++) {
            if(map[integer]>0) {
                if(bucket[map[integer]]==null) bucket[map[integer]]=new ArrayList<Integer>();
                bucket[map[integer]].add(integer);
            }
        }                                                             
        for(int count = nums.length; count>0; count--){
            if(bucket[count]!=null)
                for(int integer: bucket[count]) {
                	result.add(integer+min);
                	if(--k==0) return result;
                }                
        }
        return result;
    }

Log in to reply
 

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