C# solution: quick selection


  • 0
    B
    public class Solution 
    {
        public int FindKthLargest(int[] nums, int k) 
    	{
    		var n = nums.Length;
            var kthSmallest = n - k + 1;
    		var kthSmallestIndex = kthSmallest - 1;
    
    		return FindKthSmallest(nums, kthSmallestIndex, 0, nums.Length - 1);
    
        }
    
    	private int FindKthSmallest(int[] nums, int kIndex, int left, int right)
    	{
    		var pivotIndex = left;
    		var pivot = nums[pivotIndex];
    
    		var preLeft = left;
    		var preRight = right;
    
    		while(left < right)
    		{
    			// Find the first which is less than pivot
    			while(left < right && nums[right] >= pivot)
    			{
    				right--;
    			}
    
    			// Find the first which is larger than pivot
    			while(left < right && nums[left] <= pivot)
    			{
    				left++;
    			}
    
    			if (left != right)
    			{
    				var temp = nums[left];
    				nums[left] = nums[right];
    				nums[right] = temp;
    			}
    		}
    
    		// replace the pivot
    		nums[pivotIndex] = nums[left];
    		nums[left] = pivot;
            
    		if (kIndex == left) return nums[left];
    		else if (kIndex < left) return FindKthSmallest(nums, kIndex, preLeft, left - 1);
    		else return FindKthSmallest(nums, kIndex, left + 1, preRight);
    	}
    }
    

Log in to reply
 

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