# 描述
在一个长度为 n+1 的数组中所有的数字都在 1~n 范围内，所以数组中至少有一个数字是重复的。
请至少找出数组中任意一个重复的数字，但不能修改输入的数组。
# 思路
采用二分法查找，时间复杂度为 O(nlogn)
在数字 1~n 中取中间值 m = (1+n) / 2, 此时数字包括 1~m, m+1~n 两段；
遍历数组，获得数字 1~m 的个数;
如果数字 1~m 的个数大于 m，说明 1~m 这一段内肯定有重复数字，那么在这一段内继续取中间值比较；
如果数字 1~m 的个数等于 m，这一段不一定有重复数字，比较后一段；
如果数字 1~m 的个数小于 m，说明 m+1~n 这一段一定有重复数字，在后一段取中间值比较；
按照上述方法一直取中间值比较，直到只剩一个数字且这个数字出现次数超过 1 ，该数字即为重复数字
# 解决
def find_dux_num(seq):
if len(seq) <= 1 or seq is None:
return None
start, end = 1, len(seq) - 1 # 获取数字1，n
while start <= end:
mid = (start+end) // 2 # 获取中间数字
count = count_num(seq, start, mid) # 计算[start, mid]数字之间的数目
# 当只取到一个数字时，如果该数字出现数目大于1，就是重复数字
if start == end:
if count > 1:
return start
else:
break
# 如果count数目 > 中间数字到起始数字之差，一定存在重复数字，继续在这一段中求中间数比较
if count > mid - start + 1:
end = mid
# 否则在后一段中求中间数比较
else:
start = mid + 1
return None
def count_num(seq, start, end):
count = 0
for i in seq:
if start <= i <= end:
count += 1
return count
if __name__ == '__main__':
print(find_dux_num([1, 2, 3, 4, 3]))
