4ms concise C++ solution using the partion idea of quicksort


  • 1
    Z

    The difference with the quicksort is just that we can ignoe a part after partition and we can stop if the partion privot is the result;So it is just a little different with quicksort

     class Solution {
        public:
        	int aim;
            int findKthLargest(vector<int>& nums, int k) {
        		aim=k-1;
                return find(0,nums.size()-1,nums);
            }
        	int find(int m,int l,vector<int>& nums){
        		if(m>=l) return nums[m];
        		int p=m;
        		for(int i=m+1;i<=l;i++){
        			if(nums[i]>=nums[m])  swap(nums[++p],nums[i]);
        		}
        		swap(nums[p],nums[m]);
        		if(p-m==aim)  return nums[p];
        		else{
        			if(p-m<aim){
        				aim-=p-m+1;
        				return find( p+1,l,nums);
        			}
        			else  return find(m,p-1,nums);
        		}
        	}
        };

  • 0
    E

    I have a question: if given [3,2,6,5,6,4] and k = 2, we should return 5 or return 6 ? The second largest is 5.


  • 0
    Z

    As the question say that note that it is the kth largest element in the sorted order, not the kth distinct element,so just 6


Log in to reply
 

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