14. 不修改数组找出重复的数字

Question

给定一个长度为 n+1
的数组nums，数组中所有的数均在 1∼n的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

数据范围
1≤n≤1000

样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。
思考题：如果只能使用 O(1)的额外空间，该怎么做呢？

Ideas

• 哈希表，遍历整个数组，判断是否有元素在哈希表中，如果在，该元素就是重复元素，否则加入哈希表。时间复杂度O(n)，空间复杂度O(n)
• 利用题目性质，由于题目中的数组长度为n+1，数组元素的范围是[1, n]，那么必然有一个数字是重复的。（抽屉原理：有n+1个苹果，放在n个抽屉里，那么至少有一个抽屉里面有2个苹果。对应到本题就是有n+1个数字，每个数字的范围是[1,n]，那么至少有一个数字出现了两次）。接着我们可以考虑如何利用这个性质。从区间角度出发，我们将整个数组划分为左右区间，如果重复的数字在左区间，那么左区间元素的个数一定>左区间的长度，右区间同理。这样问题可以依据是否存在重复元素划分，就有了两段性，就可以利用二分。注意，这里我们二分的是数值的范围[1,n]，而不是区间的长度，因为我们要找的是重复的数字。具体做法为：将区间划分为两个子区间[l,mid], [mid+1, r]计算任意一个区间的元素的个数cnt，与当前区间的长度进行对比，如果cnt>区间长度，那么该区间存在重复元素，否则另外一个区间存在重复元素。最终返回的是数值范围l，而不是nums[l]。时间复杂度O(logn)，空间复杂度O(1)

Code

class Solution(object):def duplicateInArray(self, nums):""":type nums: List[int]:rtype int"""# 哈希表 时间复杂度O(n), 空间复杂度O(n)# s = set()# for i in nums:#     if i in s:#         return i#     s.add(i)# 抽屉原理：n+1个苹果放在n个盒子中，那么至少存在一个盒子有两个苹果# 将数值范围区间划分为两份，分别统计每个区间元素个数 # 如果区间元素个数>区间长度，说明重复的元素在该区间，否则就是另外一个区间# 时间复杂度O(nlogn), 空间复杂度O(1)n = len(nums) - 1l, r = 1, nwhile l < r: # [l, mid], [mid+1, r]mid = l + r >> 1# 统计[l, mid]区间中的元素个数 这里任意统计一个区间元素个数即可cnt = 0for i in nums:if i >= l and i <= mid:cnt += 1# 说明在左区间if mid - l + 1 < cnt:r = midelse:l = mid + 1return l