Java bucket O(n) soluction beats 83%


  • 1
    P
    public int findKthLargest(int[] nums, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(num, max);
            min = Math.min(num, min);
        }
        int[] bucket = new int[max - min + 1];
        
        for (int num : nums) {
            bucket[num - min]++;
        }
        
        for (int i = max - min; i >= 0; i--) {
            if (bucket[i] > 0) {
                for (int j = 0; j < bucket[i]; j++) {
                    if (k == 1) return i + min;
                    k--;
                }
            }
        }
        return -1;
        
    }

Log in to reply
 

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