leetcode-287. Find the Duplicate Number

题目：

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2] Output: 2 Example 2:

Input: [3,1,3,4,2] Output: 3 Note:

You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

题目描述：

给一个序列，n+1个int类型数，范围在1-n之间，有一个数会重复一次以上，一定存在且近存在一个这样的数，找出它。 要求，O(1)空间，O(n^2)时间，数组不可改变。

思路

首先想到的就是排序，按顺序找，或者二分之类的方法，但是排序会改变数组不可以用。

方法1：

还有一个方法容易想法，就是两个for循环也满足要求。时间复杂度O(N^2),空间O(1)，但是显然这样的话这题没啥意思。

方法2：另一个方法其实是把数组当成一个循环链表。为什么这么想，数组内的数字都是在1-n之间的，从下标0开始，把它的内容当成下一次的下标，依次寻找内容总会在数组下标里，不理解看例子。

例如： 0 1 2 3 4 1 3 4 2 2 从0开始，nums[0]=1,nums[1]=3,nums[3]=2,nums[2]=4,nums[4]=2,nums[2 =4…..一直循环下去. 然后找循环链表的入口下标就可以了，为什么是下标呢？ 比如一个环，nums[3]=2,nums[2]=4是入口的数值，一直遍历到返回入口的上一个位置，nums[4]=2,，所以入口的下标2才是重复数字。nums[3]=nums[4]=2。 怎么找链表的入口地址，参照leetcode：142. Linked List Cycle II 地址：https://blog.csdn.net/qq_33278461/article/details/80100233

code

class Solution { public: //方法1 int findDuplicate(vector<int>& nums) { for(int i=0;i<nums.size()-1;++i){ for(int j=i+1;j<nums.size();++j){ if(nums[i]==nums[j]){ return nums[i]; } } } } //方法2. int findDuplicate(vector<int>& nums) { int fast=nums[nums[0]],slow=nums[0]; while(fast!=slow){ fast=nums[nums[fast]]; slow=nums[slow]; } slow=0; while(slow!=fast){ slow=nums[slow]; fast=nums[fast]; } return fast; } };