The time is O(n^2),but why I.M told that time limit exceeds


  • 0
    L
    class Solution {
    public:
    
    void sort(vector<int> &numbers,int left,int right){
            int i=left,j=right;
            int temp;
            if(left>=right) return ;
            while(i<j){
                 temp=numbers[left];
                while(numbers[j]>temp&&j>i) j--;
                    if(j>i) {
                        numbers[i]=numbers[j];
                        i++;
                        }
                while(numbers[i]<temp&&j>i) i++;
                    if(j>i) {
                        numbers[j]=numbers[i];
                        j--;
                        }
            numbers[i]=temp;
            sort(numbers,left,i-1);
            sort(numbers,i+1,right);// it is in while-loop, not out of it.
            }
       }
    
        int threeSumClosest(vector<int> &num, int target) {
            int sum=0;int gap,mgap;
        
            if (num.size()<3) return -1;
            
            int i,j,k;
            
            sort(num,0,num.size()-1);
            for(int i=0;i<=num.size()-3;i++){
                int j=i+1,k=num.size()-1;
                sum=num[j]+num[i]+num[k];
                    gap=sum-target;
                    mgap=gap;
                while(j<k){
                    sum=num[j]+num[i]+num[k];
                    gap=sum-target;
                    if(gap<mgap) mgap=gap;
                    if(num[j]+num[i]+num[k]>0)   k--;
                    else   j++;
                }
               
            }
             return sum;
        }
            
            
       
    };

  • 1
    S

    First, you need to make sure your 'sort' function runs correctly. Consider replacing it with std::sort and see how it works.

    The biggest problem of your code is that it doesn't seem to have a mechanism to store the closest sum when you find it. As a matter of fact, what you are returning now is ALWAYS the sum of the last three numbers. Also, when you calculate the difference between 'sum' and 'target', be sure to take its absolute value. Otherwise you won't find the 'closest sum'.


  • 0
    L

    i correct the mistakes above,and accepted(but use the sort function of the system),but i wanna know that why the time always exceeds when i use the sort func of my own?
    ps,i use the quicksort.


  • 0
    S

    It is very easy to make off-by-one mistakes in a quicksort implementation, so you may want to test this function thoroughly to make sure it indeed works. However, even if it works, it still seems that your quicksort implementation is an sub-optimal one: you always choose the first element in the sequence as the pivot. If the sequence is already sorted, then this implementation would end up in the worst-case running time -- O(n^2).


  • 0
    L

    but the key point is that the array is unknown to me,so you mean it's not a good idea to write it on my own? is there any possible way to improve ?


  • 0
    S

    It is always good to practice implementing qsort on your own. However, from a practical point of view, your own implementation is very unlikely to be as fast as std::sort. A simple improvement could be to always choose the middle value, as opposed to the first element, as the pivot. For an even more efficient implementation, you may want to read about 'IntroSort', and more advanced partitioning algorithms.


  • 0
    L

    thank you so much ~!! i learn a lot from it O(∩_∩)O


  • 0
    S

    Pay attention that our Discuss is English only. I have updated your comment in code.


Log in to reply
 

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