Clean C++ Solution using Quick Select


  • 0
    W

    We first perform a partitioning over the array. This is exactly the same as that used in Quick Sort.

    After that, we know for sure that elements on the left of j are the largest (unordered), and those on the right of i are the smallest(unordered).

    Let's assume that elements exist on the left of j here. If the number of such elements exceeds k, then we just find the kth largest in this part. Otherwise, we decrease k by this amount and search in the other part of the array.

    If no elements lie on the left of j, there must be elements on the right of i. We can perform similar operations as above. Therefore, using recursion, we can always make progress till we find the target.

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            return __findKthLargest(nums, k, 0, nums.size() - 1);
        }
        
    private:
        int __findKthLargest(vector<int>& nums, int k, int start, int end) {
            if (start == end)
                return nums[start];
            int pivot = nums[(start + end) / 2];
            int i = start, j = end;
            // perform the partitioning
            while (i <= j) {
                while (nums[i] > pivot)
                    i++;
                while (nums[j] < pivot)
                    j--;
                if (i <= j) {
                    swap(nums[i], nums[j]);
                    i++, j--;
                }
            }
            // after partition, the elements left to j are the largest(unordered), and
            // the elements right to i are the smallest(unordered). However, we still 
            // need to check if i or j has gone beyond the border.
            int left = j - start + 1, right = end - i + 1;
            if (left > 0) { // the j index is valid
                if (left >= k) // there are enough elements left to j, find the kth largest there!
                    return __findKthLargest(nums, k, start, j);
                else // the kth largest must lie on the right of index j, discard the ones left to j!
                    return __findKthLargest(nums, k - left, j + 1, end);
            } else {
                if ((end - start + 1) - right >= k)
                    return __findKthLargest(nums, k, start, i - 1);
                else
                    return __findKthLargest(nums, k - (end - start + 1 - right), i, end);
            }
        }
    };

  • 0
    I

    Your partition algorithm doesnt separate greater and smaller elements of pivot.Just see the output for the following input.
    [54,20,25,24,22,1,2,3]
    2
    In the first complete run of this 'while' loop 20 will be swapped by 24(pivot) and 25 is still a greater(than pivot) element remaining on the right side.


  • 0
    W

    Hi itarun, I never said that I am seperating greater and smaller elements by the pivot. What I stressed in the post is that everything on the left of j are the largest, and everything on the right of i are the smallest. No assumption is made with elements on either side of the pivot.


  • 0
    I

    Okay,Now I get it.But doesn't this algorithm has a worst case time complexity of O(n^2) when k is of order of n and everytime you have a skewed partition.While forming a heap and then doing deletion k time will give a worst case O(nlogn) even if k is order of n?


  • 0
    W

    Absolutely. Quick Select is known to have an amortized runtime O(n) and worst case runtime O(n^2).


Log in to reply
 

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