C++ mergesort 36ms


  • 0
    X

    class Solution {

    public:

        bool containsDuplicate(vector<int>& nums) {
        if(nums.size()==0){
            return false;
        }
        return mergeSort(nums,0,nums.size());  
        }
    
       bool mergeSort(vector<int>& nums,int i,int j){  // i <  <=j
           if(j-i<2) return false;
           int k=i+j>>1;
           if(mergeSort(nums,i,k)||mergeSort(nums,k,j)||merge(nums,i,k,j)){
                return true;
           }
               return false;
        }
        bool merge(vector<int>& nums,int i,int k,int j){
            int p=i+1,q=k+1;
            while(p<q&&q<=j){
                if(nums[p-1]==nums[q-1]){
                    return true;
                }else{
                    if(nums[p-1]<nums[q-1]){
                        p++;
                    }else{
                        nums.insert(nums.begin()+p-1,nums[q-1]);
                        nums.erase(nums.begin()+q);
                        p++;
                        q++;
                    }
                }
            }
        return false;
    }
    

    };


Log in to reply
 

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