A summary: maxHeap, selectionSort, sorting, recursion and partition methods


  • 2

    partition

    int findKthLargest(vector<int>& nums, int k) 
    {
        int left=0, right=nums.size()-1;
        while(true)
        {
            int pos=partition(nums, left, right);
            if(pos==k-1)  return nums[pos];
            if(pos>k-1)   right=pos-1;
            else left=pos+1;
        }
    }
    
    int partition(vector<int>& nums, int left, int right)
    {
        int pivot=nums[left];
        int l=left+1, r=right;
        while(l<=r)
        {
            if(nums[l]<pivot && nums[r]>pivot) swap(nums[l++], nums[r--]);
            if(nums[l]>=pivot) l++;
            if(nums[r]<=pivot) r--;                                               
        }
        swap(nums[left], nums[r]);
        return r;
    }
    

    recursive

    int findKthLargest(vector<int>& nums, int k) 
    {
        int n = nums.size();
        if (n==1) return nums[0];
        int big = nums[0], small = big;
        vector<int> left;
        vector<int> right;
        for (int i = 1; i < n; i++) 
        {
            if (nums[i] > big) big = nums[i];
            if (nums[i] < small) small = nums[i];
        }
        const double mid = (big + small) / 2.0; //make the partition more even
        for (int i = 0; i < n; i++) 
        { 
            if (nums[i] <= mid) left.push_back(nums[i]);
            else right.push_back(nums[i]);
         }
        if (left.size() == n) return nums[0]; //all elements are the same
        if (left.size() >= n-k+1)
            return findKthLargest(left, k-right.size());
        else 
            return findKthLargest(right, k);
    }
    

    max heap using priority_queue

    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int, vector<int>, less<int>> maxHeap(nums.begin(), nums.end());
        for(int i = 1; i < k; ++i) maxHeap.pop();
        return maxHeap.top();
    }
    

    selection

    int findKthLargest(vector<int>& nums, int k) 
    {
        for(int i = 0; i < k; i++)
        {
            int localMax = i;
            for(int j = i+1; j < nums.size(); ++j)
                if(nums[j] > nums[localMax]) localMax = j;
            swap(nums[i], nums[localMax]);
        }
        return nums[k-1];
    }
    

    sort

    int findKthLargest(vector<int>& nums, int k) 
    {
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k-1];
    }
    

    Always welcom new ideas and practical tricks, just leave them in the comments!


Log in to reply
 

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