4ms iterative version of quick-select


  • 0
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int target = n - k;
        int left = 0, right = n - 1;
        while(1) {
            int low = left + 1, high = right, pivot = nums[left];
            while(low <= high) {
                while(high >= low && nums[high] >= pivot)
                    high--;
                while(low <= high && nums[low] < pivot)
                    low++;
                if(low < high) {
                    int temp = nums[low];
                    nums[low] = nums[high];
                    nums[high] = temp;
                    low++;
                    high--;
                }
            }
            if(high == target)
                return pivot;
            else if(high < target) {
                left = high + 1;
            } else {
                right = high - 1;
                nums[left] = nums[high];
            }
        }
    }

Log in to reply
 

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