c# quick select solution


  • 0
    N
    public class Solution {
        public int FindKthLargest(int[] nums, int k)
        {
            return FindKthLargest(nums, 0, nums.Length - 1, k);
        }
        public int FindKthLargest(int[] nums, int left, int right, int k)
        {
            var pos = partition(nums, left, right, k);
            if (pos - left == k - 1)
            {
                return nums[pos];
            }
            else if (pos - left < k - 1)
            {
                return FindKthLargest(nums, pos + 1, right, k - (pos - left + 1));
            }
    
            return FindKthLargest(nums, left, pos - 1, k);
        }
    
        public int partition(int[] nums, int left, int right, int k)
        {
            var part = nums[right];
            var index = left;
    
            for (var i = left; i <right; i++)
            {
                if (nums[i] >= part)
                {
                    swap(nums, i, index);
                    index++;
                }
            }
    
            swap(nums, index, right);
            return index;
        }
    
        public void swap(int[] nums, int i, int j)
        {
            var temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    

Log in to reply
 

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