Accelerate the partition method from 200ms to 12ms (the best submission)


  • 1

    Once you un-comment the three lines, the magic will come into being. So shocked!

     class Solution {
        public:
            int findKthLargest(vector<int>& nums, int k) {
                int size = nums.size();
                int left=0, right=size-1;
                // srand((unsigned)time(0));
                // for(int i = 0; i < size; ++i)
                //     swap(nums[i], nums[rand()%size]);
                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;
            }
        };
    

Log in to reply
 

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