C++ solution, similar to quicksort


  • 3
    1
    int findKthLargest(vector<int>& nums, int k) {
        int size=nums.size();
        return helper(nums,k,0,size-1);
    }
    int helper(vector<int>& nums,int k,int begin,int end){
        if(begin==end) return nums[begin];
        if(end-begin==1){
            if(k==1) return max(nums[begin],nums[end]);
              else return min(nums[begin],nums[end]);
        }
        int tmp=nums[begin];
        int left=begin;
        int right=end;
        while(left<right){
            while(nums[right]>=tmp and left<right) --right;
               if(left==right) break;
                 nums[left]=nums[right];
            while(nums[left]<=tmp and left<right) ++left;
               if(left==right) break;
                nums[right]=nums[left];
        }
        nums[left]=tmp;
        int kth=end-right+1;
        if(kth==k) return nums[left];
        else if(kth < k) return helper(nums,k-kth+1,begin,left);
        else return helper(nums,k,left+1,end);
        }

Log in to reply
 

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