Description
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space.
Example 1:
Input: nums = [1,1,2,3,3,4,4,8,8] Output: 2
Example 2:
Input: nums = [3,3,7,7,10,11,11] Output: 10
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 105
Solutions
Solution 1: Binary Search
The given array nums is sorted, and we need to find the element that appears only once in O(log n) time. Therefore, we consider using binary search to solve this problem.
We define the left boundary of the binary search as l = 0 and the right boundary as r = n - 1, where n is the length of the array.
In each step, we take the middle position mid = (l + r) / 2. If the index mid is even, we should compare nums[mid] with nums[mid + 1]. If the index mid is odd, we should compare nums[mid] with nums[mid - 1]. Therefore, we can uniformly compare nums[mid] with nums[mid \oplus 1], where \oplus denotes the XOR operation.
If nums[mid] ≠ nums[mid \oplus 1], then the answer is in [l, mid], so we set r = mid. If nums[mid] = nums[mid \oplus 1], then the answer is in [mid + 1, r], so we set l = mid + 1. We continue the binary search until l = r, at which point nums[l] is the element that appears only once.
The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).
class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: l, r = 0, len(nums) - 1 while l < r: mid = (l + r) >> 1 if nums[mid] != nums[mid ^ 1]: r = mid else: l = mid + 1 return nums[l](code-box)
