java 2ms beats 96% based on counting sort O(n)


  • 0
    W
    public class Solution {
        public int findKthLargest(int[] nums, int k) {
    		int max=nums[0];
    		int min=nums[0];
    		for(int i=1;i<nums.length;i++){//n
    			if(nums[i]>max) max=nums[i];
    			else if(nums[i]<min) min=nums[i];
    		}
    		int[] counts=new int[max-min+1];
    		for(int i=0;i<nums.length;i++){//n
    			counts[nums[i]-min]++;
    		}
    		int large=0;
    		for(int i=counts.length-1;i>=0;i--){
    			k-=counts[i];
    			if(k<=0) {
    				large = i+min;
    				break;
    			}
    		}
    		return large;
        }
    }
    

  • 1
    C

    This is a nice solution, actually this is not a strict o(n) solution, if you mean n is num of elements in the array. The counts[] array size will go up to Integer.MAX_VALUE. But this will be efficient when n is very big.


Log in to reply
 

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