Approach #1 Binary search [Accepted]
Intuition
It is a search problem request O(log n) time and O(1) space
Algorithm
Binary search is suitable method for search problem and its
time cost is O(log n)
The basic idea is that the single element is not the same as the left one and
the right one.
First, if the length of array is 1, the only element is the answer we are looking
for.If not, we do as follows.First We find the middle one of array,and assume if it
is single element or not.If it is not the single element, there are four possibilities.
Shown as follows:
Divide parts is odd and right one is different:[1 1 2 2 3 3 5] The middle element
is 2, it divides the array into two parts,[1 1 2] and [3 3 5](contain 3(odd) elements)
right of middle element is 3 which is not equal to 2. The answer is in [3 3 5].
Divide parts is odd and left one is different:[1 1 2 3 3 5 5],parts are [1 1 2] and
[3 5 5],the answer is [1 1 2]
Divide parts is even and right one is different:[1 2 2 3 3 5 5 6 6],parts are [1 2 2 3]
and [5 5 6 6],answer is in [1 2 2 3] which contain the same number 3 as the middle one.In this
situation we just need to put [1 2 2] into recursive function
Divide parts is even and left one is different:[1 1 2 2 3 3 5 5 6],parts are [1 1 2 2]
and [3 5 5 6],then we put [5 5 6] into recursive function
Python
class Solution(object):
def singleNonDuplicate(self, nums):
if(len(nums)==1):
return nums[0]
mid_place = len(nums)//2
mid = nums[mid_place]
if (mid!=nums[mid_place-1] and mid!=nums[mid_place+1]):
return mid
if(mid_place%2==0):
if (mid!=nums[mid_place-1]):
return self.singleNonDuplicate(nums[mid_place+2:])
return self.singleNonDuplicate(nums[:mid_place-1])
if (mid!=nums[mid_place-1]):
return self.singleNonDuplicate(nums[:mid_place])
return self.singleNonDuplicate(nums[mid_place+1:])
Complexity Analysis
- Time complexity : O(log n).
- Space complexity : O(1).