4ms java solution | Concise Randomized Quick Select implemention


  • 0
    R
    public class Solution {
    
    public int findKthLargest(int[] nums, int k) {
    	if (nums == null || k <= 0 || k > nums.length)
    		return -1;
    	int i = 0, j = nums.length - 1;
    	while (true) {
    		int pivot = partition(nums, i, j);
    		if (pivot + 1 == k)
    			return nums[pivot];
    		if (pivot + 1 < k)
    			i = pivot + 1;
    		else
    			j = pivot - 1;
    	}
    }
    
    private int partition(int[] a, int start, int end) {
    	swap(a, (int) (Math.random() * (end - start + 1)) + start, end);
    	int i = start;
    	for (int j = start; j < end; j++) {
    		if (a[j] > a[end])
    			swap(a, i++, j);
    	}
    	swap(a, i, end);
    	return i;
    }
    
    private void swap(int[] a, int i, int j) {
    	int temp = a[i];
    	a[i] = a[j];
    	a[j] = temp;
    }
    

    }


  • -1
    C

    4ms, 2 lines of Java

    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            Arrays.sort(nums);
            
            return nums[nums.length -1 -(k-1)];
        }
    }

  • 0
    R

    Its correct but time complexity of your solution is O(nlogn) + O(logn) stack space assuming the sort method uses merge sort. The QuickSelect Algorithm allows you to find kth largest number on O(n) amortized time.


Log in to reply
 

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