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 {
            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]);
                    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;
                    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.