C++,32ms, do it in place


  • 0
    X

    class Solution {
    bool partition(vector<int>& nums,int left,int right)
    {

        if(right<=left)return false;
        if(right-left==1)return nums[left]==nums[right];
        int mid = (left+right)>>1;
        int com = nums[mid];
        nums[mid]=nums[right];
        nums[right]=com;
        int start = left, end = right-1;
        while(start<end)
        {
            while(start < end && nums[start]< com) start++;
            while(start < end && nums[end]>com)end--;
            if(nums[start]==com || nums[end]==com)return true;
            if(start<end)
            {
                int tmp = nums[start];
                nums[start]=nums[end];
                nums[end]=tmp;
                start++;
                end--;
            }
        }
        if(nums[start]>com)mid = start-1;
        else mid = start;
        return partition(nums,left,mid ) || partition(nums,mid+1 ,right-1);
    }
    

    public:

    •  bool containsDuplicate(vector<int>& nums) {
        if(nums.size()<2)return false;
        return partition(nums,0,nums.size()-1);
      
      }
      };

Log in to reply
 

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