有一种非常诡异的算法，就是采用类似于单链表是否存在环的问题。“判断单链表是否存在环”是一个非常经典的问题，同时单链表可以采用数组实现，此时每个元素值作为next指针指向下一个元素。本题可以转换化为“已知一个单链表中存在环，找出环的入口点”这种想法。具体思路如下：将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，则该题不可直接采用该方法。程序示例代码如下：
#include "stdafx.h"
#include <stdio.h> int FindInteger(int array[], int n)
{
int x, y;
x = y = 0;
do
{
x = array[array[x]];
y = array[y];
} while (x != y);
x = 0;
do
{
x = array[x];
y = array[y];
} while (x != y);
return x;
}
int main()
{
int array[] = { 1, 3, 2, 4, 5, 4 };
int length = sizeof(array) / sizeof(array[0]);
printf("%d\n", FindInteger(array, length));
getchar();
return 0;
}
效果如图：