Leetcode[540] python3 implementation of a single element in an ordered array (dichotomy, full of details)

# Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once . 
# 
# Please find and return the number that only appears once . 
# 
# The solution you design must meet O(log n) Time complexity and O(1) Spatial complexity . 
# 
# 
# 
# 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
# 
# 
# 
# 
# 
# 
# Tips : 
# 
# 
# 1 <= nums.length <= 10⁵ 
# 0 <= nums[i] <= 10⁵ 
# 
# Related Topics Array Two points search 410 0
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
if nums[mid] == nums[mid ^ 1]:
low = mid + 1
else:
high = mid
return nums[low]
# leetcode submit region end(Prohibit modification and deletion)

Refer to the official website solution . Record here to learn .

We should pay attention to examining questions , There is a sequence table , And ask the O(log(n)) Complexity , Should use dichotomy , Instead of exclusive or one by one .

You should list several scenarios yourself , Find out the rules ：

initialization low=0, high = n - 1;

Make mid = (low + high) // 2, Notice that it's not (high - low) // 2 .

1. If mid Is odd , And nums[mid] == nums[mid-1], Then the individual numbers should be on the right ;
2. If mid Is odd , And nums[mid] == nums[mid+1], Then the individual numbers should be on the left ;
3. If mid It's even , And nums[mid] == nums[mid-1], Then the individual numbers should be on the left ;
4. If mid It's even , And nums[mid] == nums[mid+1], Then the individual numbers should be on the right ;

details 1

The official solution uses a clever contrast ：

if nums[mid] == nums[mid ^ 1]：

mid It's odd ,mid ^ 1 = 0 = mid - 1;
mid For the even ,mid ^ 1 = 1 = mid + 1;

The above comparison is true , Corresponding to the first 1、4 In this case , On the right side , It should be updated low;
The above comparison is true , Corresponding to the first 2、3 In this case , On the left side , It should be updated high;

details 2

 if nums[mid] == nums[mid ^ 1]:
low = mid + 1
else:
high = mid

to update low when , Set as mid + 1;
to update high when , Set as mid;
The final result is nums[low].