C++ solution use quick sort. How to improve?


  • 0
    K

    I think this is an O(n) solution. but it runs 1169ms. why? How to improve it?

    class Solution {
    public:
        int minMoves2(vector<int>& nums) {
            int l=0,r=nums.size()-1,mid=nums.size()/2,pos;
            while(true)
            {
                pos=partation(nums,l,r);
                if(pos==mid) break;
                if(pos>mid)
                    r=pos-1;
                else
                    l=pos+1;
            }
            int res=0;
            for(int i=0;i<pos;++i)
                res+=nums[i]-nums[nums.size()-1-i];
            return res;
        }
        int partation(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;
        }
    };

  • 0

    What makes you think it's O(n)? It's not. It's only O(n2).


  • 0
    K

    @StefanPochmann The average situation: n+n/2+n/4...+1=2*n-1 O(n). but in the worst case:n+(n-1)+...1=n(n+1)/2 O(n^2). O(n) is the average time complexity. so the time depends on the test data?


  • 0

    @kupe If you mean average complexity, you should say so. Otherwise it's understood as the overall complexity, i.e., worst case complexity. Yes, the time depends on the test data, and it's easy to make you actually take quadratic time. Code like yours is actually exactly the reason why the judge tests not only large random arrays but also large sorted or reverse sorted arrays :-)


  • 0
    K

    @StefanPochmann ok,I see. My solution for problem 215"Kth Largest Element in an Array" uses the same method. Maybe there are no test cases like that. Thanks.


  • 0

    @kupe Can you show your solution for that one?


  • 0
    K

    @StefanPochmann
    kith largest element in an array

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            int left=0,right=nums.size()-1;
            while(true)
            {
                int pos=partation(nums,left,right);
                if(pos==k-1)
                    return nums[pos];
                if(pos>k-1)
                    right=pos-1;
                else
                    left=pos+1;
            }
        }
        int partation(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;
        }
    };

  • 0

    @kupe Yeah, that's also slow. Looks like there are some similar hard test cases in that problem. And your solution takes about 185 ms, while the most frequently achieved time is 16 ms.


  • 0
    K

    @StefanPochmann Yes. I tried it again and got 200ms+... Using heap sort is much better.


  • 0

    @kupe Or you could just randomize yours. If I simply add

        swap(nums[left], nums[left + rand() % (right - left + 1)]);
    

    at the start of your partation function, then your solution gets accepted in 9 ms.


  • 0
    K

    @StefanPochmann choose a random number as pivot. excellent!


  • 0

    @StefanPochmann I meet the same question,Thanks for your explanation!


Log in to reply
 

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