数组中重复的数字

然后我们在博客用最复杂的方式学会数组（Python实现动态数组）这篇博客中介绍了数组这一结构的本质，并自己动手实现了一个动态数组。

今天我们介绍一下另一道来自《剑指Offer》的关于数组的面试题——不修改数组找出重复的数字。

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

题目二：不修改数组找出重复的数字

给定一个长度为 n+1 的数组里的所有数字都在 0～n 的范围内，所以数组中至少有一个数字是重复的。

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

样例：

给定长度为8的数组 nums = [2， 3， 5， 4，3， 2， 6，7]

那么输出重复的数字2或者3

思路

首先我们得关注到，题目要求是：不修改数组，然后还是 返回任意一个重复的数字 。所以解题思路相比而言变少了：

1. 哈希表：跟上一题一样，本题也可以创建一个哈希表，如果原数组的每个数字第一次出现，就把他放到哈希表中去，即原数组大小为m的数字应该放到哈希表下标为m的位置上。空间复杂度是 O(n)
2. O(n) 。
3. 二分法：那么有没有不用空间复杂度O(n)
4. O(n) 的算法。假设没有重复数，那么 1~n 之间，每个数都只能出现一次。而题目中，这个数组至少有一个数字重复，即出现的次数大于1。
5. 利用二分的思想：把 1~n 的数字从中间数字m开始分为两部分，前一半为 1~ m，后面一半为 m+1 ~n，如果 1~m 中的数字在数组中出现的次数大于m，那么这一半必定有重复的数字；否则，那么另一部分必定含有重复数字。接着我们，继续对含有重复数字的区间一分为二，直到找到重复的数字。

思路一：哈希表

def find_duplicated_num(nums):
 """hash_map"""
 hash_map = dict()
 for i, val in enumerate(nums):
 if val in hash_map:
 return val
 hash_map[val] = i
 return False

思路二：二分法

def reduce_inter(nums2, left, right):
 """ """
 mid = (left + right) // 2
 count = 0
 length = len(nums2)
 for i in range(length):
 if (nums2[i] >= left) and (nums2[i] <= mid):
 count += 1
 if count > mid - left + 1:
 return left, mid
 else:
 return mid+1, right
def find_duplicated_num2(nums2):
 left, right = 1, len(nums2) - 1
 while left != right:
 left, right = reduce_inter(nums2, left, right)
 return left

测试

nums = [2, 3, 5, 4, 3, 2, 6, 7]
# nums_n = [5, 4, 3, 2, 6, 7]
print("思路一测试结果: ", find_duplicated_num(nums))
print("思路二测试结果: ", find_duplicated_num2(nums))

结果

思路一测试结果: 3
思路二测试结果: 3

总结

其实，这种算法不能保证找出所有重复的数字，比如不能找出[2, 3, 5, 4, 3, 2, 6, 7]重复数字2。

最后，小编想说：我是一名python开发工程师，整理了一套最新的python系统学习教程，想要这些资料的可以关注私信小编“01”即可，希望能对你有所帮助