1ms Java Code with Quick Select


  • 0

    Quick sort can solve this, but we don't need to sort both two sides.
    time complexity is O(n)

            public Integer findKthLargest(int[] nums, int k) {
    		if (nums == null || k > nums.length) 
    			return null;
    		int len = nums.length;
    		int index = len - k;
    		return quickSelect(nums, 0, len - 1, index);
    	}
    	
    	private int quickSelect(int[] nums, int left, int right, int index) {
    		if (left == right)
    			return nums[left];
    		int mid = (left + right) / 2;
    		int pivot = nums[mid];
    		nums[mid] = nums[left];
    		int i = left, j = right;
    		while (i < j) {
    			while (i < j && nums[j] > pivot) j --;
    			if (i == j) break;
    			nums[i] = nums[j]; i ++;
    			while (i < j && nums[i] < pivot) i ++;
    			if (i == j) break;
    			nums[j] = nums[i]; j --;
    		}
    		nums[i] = pivot;
    		if (i == index) return nums[index];
    		if (i > index) return quickSelect(nums, left, i - 1, index);
    		return quickSelect(nums, i + 1, right, index); 
    	}

  • 0
    M

    可啪,无处不在的膜法师……


Log in to reply
 

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