Java Quick Select Solution, recursion way and iteration way


  • 0
    M
    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            final int N = nums.length;
            // return quickSelect(nums, N-k, 0, N-1);
            return quickSelect(nums, N-k);
        }
        // recursion way
        private int quickSelect(int[] nums, int k, int start, int end){
            int idx = partition(nums, start, end);
            if(idx>k){
                return quickSelect(nums, k, start, idx-1);
            } else if(idx<k){
                return quickSelect(nums, k, idx+1, end);
            } else {
                return nums[idx];
            }
        }
        // iteration way
        private int quickSelect(int[] nums, int k){
    	int start=0, end=nums.length-1;
    	while(true){
    	    if(start>=end) return nums[start];
    	    int idx = partition(nums, start, end);
    	    if(idx<k){
    	    	start = idx+1;
    	    } else if(idx>k){
    		end = idx-1;
    	    } else {
    	    	return nums[k];
    	    }
    	}
        }
        
        private int partition(int[] nums, int start, int end){
            int pivotVal = nums[start];
            int j=start+1;
            for(int i=start+1; i<=end; i++){
                if(nums[i]<pivotVal){
                	swap(nums, i, j);
                    j++;
                }
            }
            j--;
            swap(nums, start, j);
            return j;
        }
        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.