MinHeap and QuickSelect


  • 0
    N

    1 Sorting
    Time Complexity: worst O(nlogn)
    The naive way is to sorting entire array and select the desired entry.

    2 MinHeap
    Time Complexity: worst O(nlogk)
    Run Time: 4ms

    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int> > pq;
        int i;
        for (i = 0; i < k; i++) {
            pq.push(nums[i]);
        }
        
        for (i = k; i < nums.size(); i++) {
            pq.push(nums[i]);
            pq.pop();
        }
        
        return pq.top();
    }
    

    When thinking about a problem, I would always first consider if any built-in data structure may help in the problem
    The "kth element" indicates the element would be "smallest in k elements". Here MinHeap naturally comes up. So we just need to maintain a pq with k elments all the time and at last return the top one.

    3 QuickSelect
    Time Complexity: average O(n) worst case O(n ^ 2)
    Run Time: 36ms

    int findKthLargest(vector<int>& nums, int k) {
        return recursion(nums, nums.size() + 1 - k, 0, nums.size() - 1);
    }
    
    int recursion(vector<int>& nums, int k, int start, int end) {
        if (start == end) return nums[start];
    
        int pivot = partition(nums, start, end);
        int order = pivot - start + 1;
        
        if (order == k) return nums[pivot];
        if (order > k) return recursion(nums, k, start, pivot - 1);
        else return recursion(nums, (k - order), pivot + 1, end);
    }
    
    int partition(vector<int>& nums, int start, int end) {
        if (start == end) return start;
        int p = nums[start];
        int i = start + 1, j = end;
        while (i <= j) {
            if (nums[i] <= p) {
                i++;
            } else if (nums[j] > p) {
                j--;
            } else {
                swap(nums[i++], nums[j--]);
            }
        }
        
        swap(nums[start], nums[j]);
        return j;
    }
    

    Just use quickselect, which is same idea of QuickSort. Be careful about two points:

    1. partition function returns the index of pivot, not order statics. We should transform it and then compare with k.
    2. the problem says kth largest, tradition paritition gets smallest something.

    The quickselect is slower than MinHeap in the Submission Runtime. I think it is due to my stupid parition


Log in to reply
 

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