算法
(整数二分模板) $O(nlogn)$
按数组里数的大小进行二分而不是数的下标
把区间划分为[l,mid],[mid+1,r]
统计左半边个数,如果大于区间长度说明有重复元素,将区间更新为[l,mid],反之更新为[mid+1,r]
Python3 代码
class Solution(object):
def duplicateInArray(self, nums):
"""
:type nums: List[int]
:rtype int
"""
l = 1
r = len(nums) - 1
while l < r:
mid = l + r >> 1
# 统计左半边数的个数
s = 0
for i in nums:
if l <= i <= mid:
s += 1
if s > mid - l + 1: # 区间长度
r = mid
else:
l = mid + 1
return l