Python question brushing - bit operation, zip (* \u) Small applications of

1. Use XOR operation to simplify parity judgment

540. A single element in an ordered array

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 <= 105
• 0 <= nums[i] <= 105

thought ： Because the whole array is ordered , Then pick a random location ,  If a single number appears before this position , that 2 Count one group 2 The rule of counting a group will be broken , Judging from this . Use bisection to find the number in the middle each time .

class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
ret = 0
low, high = 0, len(nums)-1
if len(nums) < 3:
return nums[0] if len(nums) == 1 else 0
if nums[0] != nums[1] and nums[1] == nums[2] or nums[len(nums)-1] != nums[len(nums)-2] and nums[len(nums)-2]==nums[len(nums)-3]:
return nums[0] if nums[0] != nums[1] else nums[len(nums)-1]
while True:
temp = (low+high)//2
if temp //2 == temp /2:
if nums[temp] == nums[temp+1]:
low = temp-1
elif nums[temp-1] == nums[temp]:
high = temp
else:
break
else:
if nums[temp] == nums[temp + 1]:
high = temp - 1
elif nums[temp-1] == nums[temp]:
low = temp + 1
else:
break
return nums[temp]

Official simplified code  

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]
author ：LeetCode-Solution
link ：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/solution/you-xu-shu-zu-zhong-de-dan-yi-yuan-su-by-y8gh/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

2. Yes zip(*__) Small application of

1380. The lucky number in the matrix

To give you one  m * n  Matrix , The number in the matrix   Each are not identical  . Please press   arbitrarily   Return all the lucky numbers in the matrix in order .

Lucky number refers to the elements in the matrix that meet the following two conditions at the same time ：

• The smallest of all elements in the same row
• The largest of all elements in the same column

Example 1：

 Input ：matrix = [[3,7,8],[9,11,13],[15,16,17]]
 Output ：[15]
 explain ：15 Is the only lucky number , Because it is the smallest value in its row , It is also the maximum value in the column .

Ideas ： The row and column of a two-dimensional array are maximized  

But note that we can easily use min（） Function to find the maximum value of an array row , But if you need to find the maximum value of a column, you must loop through it , It's a lot of trouble , This is the time to use zip(*__) To extract a column （ My previous blog said ）

# Simplified code
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
ret = []
for i in matrix:
for j,num in enumerate(i):
if num == min(i) and num == max([i for i in zip(*matrix)][j]): # Remember this method , Take the maximum value of a column in a two-dimensional array
ret.append(num)
return ret
matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
print([i for i in zip(*matrix)][0]) # (1, 9, 15)