287  一个数组的元素为1~n，其中若干个数被一个数代替了，找出这个数

                                                                                                                                                   点击此处返回总目录

【题目】

【分析】

乍一看这道题没什么。但是看了说明，就有点崩溃，很多路都被堵死了。

1.不能更改原数组。就不能使用以下方法来做：

   a. 对数组排序，一趟遍历搞定（即，645题的方法四）；

   b. 通过负号来标记已经存在过该数（即，645题的方法三）；

2. 只能使用额外的o(1)的空间。就不能使用以下方法来做：

    a. 使用Set记录（即，645题的方法一）

    b. 使用数组记录（即，645题的方法二）

3. 时间复杂度小于o(n2)。就不能通过两层for循环来做。

4. 不止重复一次。就不能通过或运算来做。比如示例1和示例2，如果都是重复了一次，直接跟1,2,3,4异或就得到结果了。

【方法一：二分查找】

可以通过二分查找的思想来做。每次折半。

比如[3,1,3,4,5,2]，3出现了2次。我们要确定1,2,3,4,5中谁出现了多次。

首先分成1,2,3和4,5两半。如果1,2,3没有重复数字，且没有被别的数字代替，那1,2,3的个数应该为3，重复的数字在4,5中找。如果1,2,3被别人代替了，那1,2,3的个数应该小于3，重复的数字也在4,5中找。如果1,2,3中有重复数字，那1,2,3的个数应该大于3，重复的数字就是1,2,3中的一个。

然后把123分成12,3两半。再继续找。

代码：

结果：

也可以使用递归的写法：

结果：

【方法二】

方法二有点不好想。比如包含8个整数的数组，元素都在1-7之间。我们发现数组的下标的范围是0-6，如果把数组中每个元素的值看做记录的是下一个数的地址，那么就会构成一个链表。而且此链表必定有环。而且环的入口节点的下标就是重复的元素。

第一，为什么是链表？因为第一个节点的值属于1-7，肯定存在这个地址。所以第一个节点指向了另一个节点。另一个节点的值也是属于1-7，肯定存在这个地址，所以这个节点肯定能指向再下一个节点。。。这样一直往后串起来，就是一条链表。

但是需要注意的是，这条链表不一定含有所有的元素。有的元素可能不在这个链表里面。

第二，这个链表一定有环。为什么一定有环呢？如果没有环时什么意思，就是有一个节点指向了空。因为所有的数组的值都在1-7之间，不可能有一个元素值为null或者8,9,10..之类的。所以这个链表指不出去，只能是自己指向自己。

第三，为什么环的入口节点的下标就是重复的元素。什么是环，就是有两个元素共同指向了入口节点。因为题目中说，只有一个重复的元素，所以只可能是这个重复的元素。

代码：

结果：