4ms clean iterative quick selection in c++


  • 0
    Y
    void swap(vector<int>& nums, int l, int r){
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
    int findKthLargest(vector<int>& nums, int k) {
        int sz = nums.size();
        int l = 0, r = sz-1;
        while(l<r){
            int tail = l, curr = l+1;
            while(curr<=r){
                if(nums[curr]>=nums[l]) swap(nums, ++tail, curr);
                curr++;
            }
            swap(nums, tail, l);
            if(k == tail-l+1) return nums[tail];
            else if(k<tail-l+1) r = tail-1;
            else{
                k -= (tail-l+1);
                l = tail+1;
            }
        }
        return nums[l];
    }

  • 0
    D

    sorry but I didn't know where the function swap(vector<int> &, int, int) is. Could you tell me ?


  • 0
    Y

    sorry I forgot to put the helper function swap. I just put it in the code


Log in to reply
 

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