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

不修改数组找出重复的数字
题目描述
给定一个长度为 n+1的数组nums，数组中所有的数均在1∼n的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
数据范围
1≤n≤1000
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思考题：如果只能使用 O(1)的额外空间，该怎么做呢？
题解
抽屉原理：如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素
本题可以用抽屉原理去做，根据题意：将n+1个数的范围在1~n，一个萝卜对应一个坑，则表明至少有一个数出现了2次及以上，那么我们可以通过二分的方法，将数组中的数根据数值的大小进行二分，切记我们二分查找的依据是数组中数值的大小而不是数组下标！！！ ，数组中数的数值大小范围在1~n，那么我们以(l+r)/2为二分的判断条件，l为给定范围的最小值，r为给定范

不修改数组找出重复的数字最先出现在Python成神之路。