[recommend for beginners]clean C++ implementation with detailed explanation


  • 5
      4 ms solution
    

    CODE:

       class Solution {
        public:
            int findKthLargest(vector<int>& nums, int k) {
                //max heap method
                //min heap method
                //order statistics
                make_heap(nums.begin(), nums.end());
                int result;
                for(int i=0; i<k; i++){
                    result=nums.front();
                    pop_heap(nums.begin(), nums.end());
                    nums.pop_back();
                }
                return result;
            }
        };
    

    20MS solution

    code:

       class Solution {
        public:
            int findKthLargest(vector<int>& nums, int k) {
                /** priority_queue<int, vector<int>, less<int>> q; **/
                priority_queue<int, vector<int>> q;
                int len=nums.size();
                for(int val:nums){
                    q.push(val);
                }
                while(q.size() > len-k+1){
                    q.pop();
                }
                return q.top();
            }
        };
    

    200ms solution

    code:

      class Solution {
        public:
            int findKthLargest(vector<int>& nums, int k) {
                int left=0, right=nums.size()-1;
                while(true){
                    int pos=help(nums, left, right);
                    if(pos==k-1)  return nums[pos];
                    if(pos>k-1)   right=pos-1;
                    else left=pos+1;
                }
            }
            
            /*** return-the-position-of-the-left-element-in-the-partitioned-list ***/
            int help(vector<int>& nums, int left, int right){
                int pivot=nums[left];
                int l=left+1, r=right;
                /*** swap-the-element-to-make-the-left-bigger-right-smaller ***/
                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--;
                }
                /*** r-is-biggest-position-smaller-than-pivot ***/
                swap(nums[left], nums[r]);
                return r;
            }
        };

  • 1

    I do think the key part is that how to update

     pos>k-1   left=pos+1
     pos<k-1   right=pos-1
    

    Code :

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            int left=0, right=nums.size()-1;
            while(true){
                /*** return pivot position ***/
                int pos=help(nums, left, right);
                /** found position **/
                if(pos==k-1)  return nums[pos];
                /** the bigger contains more number **/
                if(pos>k-1)  right=pos-1;
                /** the smaller contains more number **/
                else left=pos+1;
            }
        }
        
        /*** quick-sort-based-pivot-function ***/
        int help(vector<int>& nums, int left, int right){
            int pivot=nums[left];
            int l=left+1, r=right;
            while(l<=r){
                /*** move the bigger number left and smaller number right ***/
                if(nums[l]<pivot && nums[r]>pivot)   swap(nums[l++], nums[r--]);
                if(nums[l]>=pivot)  l++;
                if(nums[r]<=pivot)  r--;
            }
            /*** swap the pivot ***/
            swap(nums[left], nums[r]);
            return r;
        }
    };

  • 0
    F

    The third solution is really cool !!


Log in to reply
 

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