学步园

56、一个含 n 个元素的整数数组至少存在一个重复数， 

请编程实现，在 O（n）时间内找出其中任意一个重复数。

/*
56、一个含 n 个元素的整数数组至少存在一个重复数， 
请编程实现，在O（n）时间内找出其中任意一个重复数。

我觉得可以用hash表存储，或者最简单的数组存储，标记；
当一个数未标记，则标记；当一个数的位置已标记，说明重复

我看网上有种算法，
采用类似于单链表是否存在环的，同时单链表可以采用数组实现
已知一个单链表中存在环，找出环的入口点”。

具体思路如下：将array[i]看作第i个元素的索引，
即array[i]——>array[array[i]]——>array[array[array[i]]]——>array[array[array[array[i]]]]——>....最终形成一个单链表，
由于数组a中存在重复元素，则一定存在一个环，且环的入口即为重复元素。

该题的关键在于，数组array的大小是n，而元素的范围是[1,n-1]，所以array[0]不会指向自己，
进而不会陷入错误的自循环。如果元素的范围中包含0。则该题不可直接采用该方法。 
如果A[i]=A[j]=x，即x在数组中出现了两次。则A[i]--->A[x]--->…---> A[j]---> A[x]，
因此链表边形成了环。

一旦链表产生后，因为重复出现得到元素恰好是环的入口点。
于是，问题就相当于单链表求环的入口点。用指针追过的办法，指针x每次步长为2，指针y每次步长为1。直到x、y相遇，
然后重置x，使x重新开始。这次同步移动x、y，每次步长都为1，当x、y再次相遇时，
恰好是环的入口点。
*/
#include<iostream>
#include<stdio.h>
using namespace std;

int FindInteger(int array[], int n)
{
	int x, y;
	x=y=0;
	do
	{
		x=array[array[x]];//判断是否环的方法 一个2步 一个1步 
		y=array[y];
	}while(x!=y);
	
	x=0;
	do
	{
		x=array[x];
		y=array[y];	//一直在循环 
	} while(x!=y);
	return x;
}

int main()						// 	   5<==4
{							  //	  ||  ||
	int array[]={1,3,2,4,5,4};//1=>3=>4=>5=>4=>5=>4 ...
	int length = sizeof(array)/sizeof(array[0]); 
	printf("%d\n",FindInteger(array,length)); 
	return 0;
}