Randomized Quick Select Clean Code


  • 0
    Z
    public int findKthLargest(int[] nums, int k) {
    	int left = 0, right = nums.length - 1, target = nums.length - k;
    	Random random = new Random();
    	while(left <= right) {
    		int index = partition(nums, left, right, random.nextInt(right - left + 1) + left);
    		if(index == target) return nums[index]; // found
    		if(index > target) right = index - 1;
    		else left = index + 1;
    	}
    	return -1; // k is not valid
    }
    private int partition(int[] nums, int start, int end, int pivot) {
    	swap(nums, pivot, end);
    	pivot = end--;
    	while(start <= end) {
    		if(nums[start] < nums[pivot]) start++;
    		else swap(nums, start, end--);
    	}
    	swap(nums, start, pivot);
    	return start;
    }
    private void swap(int[] nums, int i, int j) {
    	int tmp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = tmp;
    }
    
    

Log in to reply
 

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