java quick select


  • 0

    quick select

    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            int start = 0;
            int end = nums.length - 1;
            
            while(start < end) {
                int pos = partition(nums, start, end);
                if(nums.length - k == pos){
                    // found
                    break;
                } else if(pos < nums.length - k) {
                    start = pos + 1;
                } else {
                    end = pos - 1;
                }
            }
            
            return nums[nums.length - k];
        }
        
    	public int partition(int[] arr, int start, int end) {
    		int index = start;
    		int pivot = arr[start];
    		for(int i = start + 1; i <= end; i++){
    			if(arr[i] < pivot && ++index != i) {
    				swap(arr, i, index);
    			}
    		}
    		swap(arr, start, index);
    		return index;
    	}
        
        
        private void swap(int[] nums, int i1, int i2) {
            int temp = nums[i1];
            nums[i1] = nums[i2];
            nums[i2] = temp;
        }
    }
    

Log in to reply
 

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