C# Quick Select O(n) Runtime


  • 0
    K
    public class Solution {
        public int FindKthLargest(int[] nums, int k) {
            k = nums.Length - k;
            int low = 0;
            int high = nums.Length - 1;
            int index = partition(nums, low, high);
            while(index != k){
                if(index > k){
                    high = index - 1;
                }
                else if (index < k){
                    low = index + 1;
                }
                index = partition(nums, low, high);
            }
            
            return nums[index];
        }
        
        private int partition(int[] nums, int low, int high){
            int k = nums[low];
            int j = low + 1;
            for(int i = low + 1; i <= high; ++i){
                if(nums[i] < k){
                    int tmp = nums[j];
                    nums[j++] = nums[i];
                    nums[i] = tmp;
                }
            }
            int tmp2 = nums[j - 1];
            nums[j - 1] = k;
            nums[low] = tmp2;
            return j - 1;
        }
    }
    

Log in to reply
 

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