Why the sort so fast?why not quicksort? Because of the size of n?


  • -3
    L
    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> vNum=nums;
            sort(vNum.begin(),vNum.end());   // This way used time is 8ms
            //QuickSort(vNum,0,vNum.size()-1);  This way used time is 300ms
            int nFirstPos=0,nSecondPos=vNum.size()-1;
            vector<int> vResult;
            while(nFirstPos<nSecondPos)
            {
                if(target==vNum[nFirstPos]+vNum[nSecondPos])
                {
                    int flag=0;
                    for(int i=0;i<nums.size();++i)
                    {
                        if(vResult.size()==2)
                            break;
                        if(nums[i]==vNum[nFirstPos])
                        {
                            vResult.push_back(i);
                        }
                        else if(nums[i]==vNum[nSecondPos])
                        {
                            vResult.push_back(i);
                        }
                    }
                    return vResult;
                }
                else if(target<vNum[nFirstPos]+vNum[nSecondPos])
                {
                    --nSecondPos;
                }
                else 
                {
                    ++nFirstPos;
                }
            }
            return vResult;
        }
        void QuickSort(vector<int>& nums,int nBegin,int nEnd)
        {
            int i=nBegin,j=nEnd;
            if(i<j)
            {
                int i=nBegin,j=nEnd;
                int temp=nums[i];
                while(i<j)
                {
                    while(i<j&&nums[j]>temp)
                    {
                        --j;
                    }
                    if(i<j)
                    {
                	    nums[i++]=nums[j];
                    }
                    while(i<j&&nums[i]<temp)
                    {
                       ++i;
                    }
                    if(i<j)
                    {
                        nums[j--]=nums[i];
                    }
                }
                nums[i]=temp;
                QuickSort(nums,nBegin,i-1);
                QuickSort(nums,i+1,nEnd);   
           }
        }
    
       
    };
    

    why the sort so fast?


Log in to reply
 

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