先写下自己的做法吧，虽然违规了。首先是对数组排序，让所有元素按升序排列。之后使用二分法查找，判断的依据是当前节点的索引值+1与当前节点值的大小关系。可以考虑如果不存在重复数，完成排序后的数组，某一节点的值与当前索引值+1应当是保持一致。当数组中出现重复数，该重复数会将大于自己的数的索引向后挤压。通过这一原理可以实现查找，贴代码

 1 class Solution {
 2 public:
 3     int findDuplicate(vector<int>& nums) 
 4     {
 5         vector<int> newNums = nums;
 6         sort(newNums.begin(),newNums.end());
 7         int p = 0;
 8         int q = newNums.size()-1;
 9         while(p<q)
10         {
11             int indexMid = (p+q)/2;
12             //如果当前索引值+1小于等于节点值，则表示当前节点前方不存在重复值，即便当前值就是重复值，也一定是第一个重复值，p向后并不影响结果
13             if(indexMid+1<=newNums[indexMid])
14             p = indexMid+1;
15             //else if(indexMid+1>newNums[indexMid])
16             //q = indexMid;
17             else
18             q = indexMid;
19             //return newNums[indexMid];
20         }
21         return newNums[q];
22     }
23 };

官方题解第一种做法，同样是二分查找，不过是统计对于某一值而言，该数组中小于等于该数的个数应当小于等于该值。该例的二分查找是对值的查找，而不是对索引的查找。代码不贴了，要看上leetcode看解析吧。

另外一种做法是龟兔赛跑的做法，把数组索引至节点值的映射看作一条边，该数组构成的图中一定存在环，因为有不止一个索引值指向同一个元素。设定快慢指针，两个指针相遇之后，将慢节点调整至0索引处，之后每次快慢指针只移动一步，下次相遇的位置就是答案。至于解释，可以想象快指针走的路程是两倍的慢指针走的路，可以假设成快指针先走到相遇处，然后慢指针与快指针一起走，直到相遇。现在想象快指针已经到了相遇点，而满指针正好从起始点出发，双方会在首先在环的起点相遇，并且相伴走到相遇点，所以，第一个相遇的点就是环的起始点。贴代码

 1 class Solution {
 2 public:
 3     int findDuplicate(vector<int>& nums) 
 4     {
 5         int slow = 0, fast = 0;
 6         do {
 7             slow = nums[slow];
 8             fast = nums[nums[fast]];
 9         } while (slow != fast);
10         slow = 0;
11         while (slow != fast) {
12             slow = nums[slow];
13             fast = nums[fast];
14         }
15         return slow;
16     }
17 };

View Code