C++ recursive


  • 0
    N

    class Solution {
    public:
    int singleNonDuplicate(vector<int>& nums)
    {
    return singleNonDuplicateR(nums, 0, nums.size());
    }

    private:
    int singleNonDuplicateR(vector<int>& nums, int begin, int size)
    {
    if(size == 0)
    {
    return -1;
    }
    if(size == 1 || size == 2)
    {
    return nums[begin];
    }
    if(size == 3)
    {
    return nums[begin + 1] == nums[begin] ? nums[begin + 2] : nums[begin];
    }
    int median = begin + (size/2);
    if(nums[median] != nums[median - 1] && nums[median] != nums[median + 1])
    {
    return nums[median];
    }
    bool nextSizeIsEven = (size/2 % 2) == 0;
    if( (nums[median] == nums[median - 1] && nextSizeIsEven) ||
    (nums[median] == nums[median + 1] && !nextSizeIsEven) )
    {
    return singleNonDuplicateR( nums, begin, nextSizeIsEven ? size/2 + 1 : size/2 );
    }
    if( (nums[median] == nums[median + 1] && nextSizeIsEven) ||
    (nums[median] == nums[median - 1] && !nextSizeIsEven) )
    {
    return singleNonDuplicateR( nums, nextSizeIsEven ? median : median + 1, nextSizeIsEven ? size/2 + 1 : size/2);
    }
    }
    };


Log in to reply
 

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