Sword finger offer (Second Edition) Python question brushing -- find any repeating element in the array

JZ3： Find any duplicate element in a one-dimensional array

```python
'''
JZ3： Enter a length of n Array of , The element value is 0-n-1, Find a repeating element in the array
Their thinking ：
1、 The boundary conditions ： An empty array / Return without repetition -1
2、 solution :
A1 After sorting, traverse and compare whether the adjacent two elements are equal
A2 Trade space for time , Use list 、 aggregate 、 Containers such as dictionaries store unique values
A3 Reorder index alignment , Match the index to the value size , Cannot correspond to a repeating element ： Traverse in turn , The elements that do not correspond are placed in the corresponding positions , Exchange value
A4 Two points search , Keep narrowing the value range , until left=right, And the length of the interval < Element number
3、 test
T1 An empty array
T2 The length is 1 Array of
T3 The length is 2 Array of
'''
from typing import List
class Solution:
def duplicate(self, numbers: List [int])->int:
''' After sorting, traverse
Time complexity : Sort nlogn + n Secondary cycle
Spatial complexity :O(1)'''
numbers.sort()
if len(numbers) == 1:
return -1
for i in range(len(numbers)):
if numbers[i] == numbers[i+1]:
return numbers[i]
return -1
def duplicate1(self, numbers: List[int])->int:
''' Use containers to store unique values
LIST/SET/DCIT
Time complexity O(n) Spatial complexity O(n)
Space for time '''
value_set = set()
for num in numbers:
if num in value_set:
return num
else:
value_set.add(num)
return -1
def duplicate2(self, numbers: List[int])->int:
'''
Index aligned array values , Reduce space complexity to O(1)
1、 Traverse the array from scratch , If the index alignment goes to the next iteration
2、 If the index is not aligned , Elements will be exchanged , Continue to compare indexes for alignment ： Each element can be swapped up to two times to align
3、 Stop conditions ： The two elements exchanged are equal 、 Duplicate element not found return -1
'''
for i in range(len(numbers)):
while numbers[i] != i:
if numbers[i] == numbers[numbers[i]]:
return numbers[i]
else:
temp = numbers[i]
numbers[i] = numbers[temp]
# Continue to compare new numbers[i] Alignment
numbers[temp] = temp
return -1
def count_range(self, numbers: List[int], left, right)->int:
if len(numbers) == 0:
return 0
count = 0
for i in range(len(numbers)):
if numbers[i]>=left and numbers[i]<=right:
count += 1
return count
def duplicate3(self, numbers: List[int])->int:
'''
1、 Value range 0~n-1： Split this interval
2、 When the number of elements is greater than the interval length , There must be repeating elements
3、 Continue to divide the interval until the interval length is 1, however count>1 when , return left/right
'''
if len(numbers) == 0:
return -1
left, right = 0, len(numbers)-1
while left <= right:
mid = (left + right) // 2
count = self.count_range(numbers, left, mid)
if left == right:
if count > 1:
return left
else:
break
if count > mid - left + 1:
right = mid
else:
left = mid + 1
return -1
if __name__ == "__main__":
solution = Solution()
# After sorting, traverse
nums = [2, 3, 1, 0, 2, 5, 3]
print(solution.duplicate(nums))
nums1 = []
print(solution.duplicate(nums1))
nums2 = [0]
print(solution.duplicate(nums2))
nums3 = [1, 1]
print(solution.duplicate(nums3))
# Use extra space to store unique values ： Space for time
print("_______"*8)
print(solution.duplicate1(nums))
print(solution.duplicate1(nums1))
print(solution.duplicate1(nums2))
print(solution.duplicate1(nums3))
# Index alignment
print("_______" * 8)
print(solution.duplicate2(nums))
print(solution.duplicate2(nums1))
print(solution.duplicate2(nums2))
print(solution.duplicate2(nums3))
# Two points search
print("_______" * 8)
print(solution.duplicate3(nums))
print(solution.duplicate3(nums1))
print(solution.duplicate3(nums2))
print(solution.duplicate3(nums3))