4ms quickselect algorithm


  • 1
    J
    int findKthLargest(vector<int>& nums, int k) {
    	return quickselect(nums, 0, nums.size() - 1, nums.size() - k);
    }
    
    int quickselect(vector<int>& nums, int left, int right, int k) {
    	if (left <= right) {
    		int pivotItem = nums[right];
    		int pos = left;
    		for (int i = left; i < right; i++) {
    			if (nums[i] < pivotItem)
    				swap(nums[i], nums[pos++]);
    		}
    
    		swap(nums[pos], nums[right]);
    
    		if (pos == k)
    			return nums[pos];
    
    		if (pos < k)
    			return quickselect(nums, pos + 1, right, k);
    		else
    			return quickselect(nums, left, pos - 1, k);
    	}
    
    	return 0;
    }

Log in to reply
 

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