6ms c++ code Quicksort


  • 3
    J
    class Solution {
    public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size()<k) return 0;
        if(nums.size()==0) return 0;
        int end = (int)nums.size()-1;
        int start = 0;
        int pivot = getPivot(nums, start, end);
        while (pivot+1!=k) {
            if(pivot<k) start = pivot+1;
            if(pivot>k) end = pivot-1;
            pivot = getPivot(nums, start, end);
        }
        return nums[pivot];
    }
    
    
    int getPivot(vector<int>& nums, int start, int end) {
        int temp;
        if(start==end) return start;
        int i=start,j=i+1;
        while (j<=end) {
            if(nums[j]>nums[start]) {
                i++;
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
            j++;
        }
        temp = nums[start];
        nums[start] = nums[i];
        nums[i] = temp;
        return i;
    }
    };

  • 3
    P

    why so complex?

    int quickSelect(vector<int>& nums, int start, int end, int k) {
        int pivot = nums[end], j = start;
        for (int i = start;i < end;++i)
            if (nums[i] > pivot)
                swap(nums[i],nums[j++]);
        swap(nums[j],nums[end]);
        if (k == j-start+1) return nums[j];
        if (k < j-start+1) return quickSelect(nums,start,j-1,k);
        else return quickSelect(nums,j+1,end,k-j+start-1);
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums,0,nums.size()-1,k);
    }

  • 0
    Z

    my 4ms c++

    class Solution {
        public:
            int findKthLargest(vector<int>& nums, int k) {
                int start=0,end=int(nums.size())-1;
                int pivot=getPivot(nums,start,end);
                 while (pivot+1!=k) {
                if(pivot<k) start = pivot+1;
                if(pivot>k) end = pivot-1;
                pivot = getPivot(nums, start, end);
                }
                return nums[pivot];
            }
            int getPivot(vector<int>& nums,int start,int end)
            {
                if(start==end) return start;
                int i=start,j=i+1;
                int temp;
                while(j<=end)
                {
                    if(nums[j]>nums[start])
                    {
                        ++i;
                        temp=nums[i];
                        nums[i]=nums[j];
                        nums[j]=temp;
                    }
                    ++j;
                }
                temp=nums[i];
                nums[i]=nums[start];
                nums[start]=temp;
                return i;
            }
        };

  • 0
    D

    you don't have to do one more swap after the for cycle, just leave the pivot at the end and move on with the rest.


  • 0
    P

    thanks! according to your suggestion, the code becomes:

    int quickSelect(vector<int>& nums, int start, int end, int k) {
        int pivot = nums[end], j = start;
        for (int i = start;i < end;++i)
            if (nums[i] > pivot)
                swap(nums[i],nums[j++]);
        if (k == j-start+1) return nums[end];
        if (k < j-start+1) return quickSelect(nums,start,j-1,k);
        else return quickSelect(nums,j,end-1,k-j+start-1);
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums,0,nums.size()-1,k);
    }

  • 0
    D

    Beautiful~, vote for your solution :)


Log in to reply
 

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