Share my heap and quick select solutions


  • 0
    S
    // quick select solution, according to the quicksort
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int l = left, r = right;
            int key = nums[l];
            
            while (l < r) {
                // find the number which bigger than pivot value from right
                while (l < r && nums[r] < key) --r;
                nums[l] = nums[r];
                
                while (l < r && nums[l] >= key) ++l;
                nums[r] = nums[l];
            }
            nums[l] = key;
            
            if (l == k - 1) return nums[k-1];
            else if (l > k - 1) right = l - 1;
            else left = l + 1;
        }
        
        // all the numbers are sorted
        return nums[k - 1];
    }
    
    // heap solution
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for (int x : nums) pq.push(x);
        for (int i = 0; i < k - 1; ++i) pq.pop();
        return pq.top();
    }

Log in to reply
 

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