287.查找重复数一个整数数组nums，其数字都在1和n之间（包括1和n），表明至少有一个重复的整数。假设只有一个重复整数，求重复数。示例1：输入：[1,3,4,2,2]输出：2示例2：输入：[3,1,3,4,2]输出：3解释：不能更改原始数组（假设数组是只读的）。只能使用额外的O(1)空间。时间复杂度小于O(n2)。数组中只有一个重复的数字，但它可能出现不止一次。解题思路：这里需要注意二分查找，如题意解释，有4条提示。这里会限制一些方法，例如：对数组进行排序，重复的数字是相邻的，你可以根据这个找到重复的数字（这违反了[原始数组不能改变]）使用哈希表，（这里违反了[仅附加O(1)算法])...上面的方法可以不受限制的使用，但是这里由于题目给的限制，暂时不考虑。先看这道题，【给定一个包含n+1个整数的数组nums，其中的数都在1到n之间（包括1和n）】，这是题中给出的前提。根据这个前提，这里二分法的思路是先设置一个值（这里也设置了[left,right]的中间值mid），但是这里要统计的是元素的个数小于或等于此mid值的原始数组（此处定义为计数）。如果count严格大于mid的值，则重复的元素会落在区间[left,mid]内。这里涉及到一个原则：抽屉原则。关于抽屉的原理，大致是这样一个现象：如果桌子上有十个苹果，我们需要把这十个苹果放到九个抽屉里。不管怎么放，我们都会发现至少会有一个抽屉，里面放着不少于两个苹果。以题目给出的例子1展开分析：[1,3,4,2,2]首先，我们知道这里的值2是一个重复值。下面，我们就按照上面的思路来分析一下。这里有5个数，即n+1=5，n=4，那么这里数组的值都在1到4之间。现在先设置一个值（根据上面说的中间值mid），这里设置为2，遍历数组，统计小于等于2的数字个数，这里可以看到有3个值，都严格大于mid，所以重复值落在区间[1,2]内。具体代码实现如下。代码实现类解决方案：deffindDuplicate(self,nums:List[int])->int:size=len(nums)left=1right=size-1whileleft
