有一种非常诡异的算法，就是采用类似于单链表是否存在环的问题。“判断单链表是否存在环”是一个非常经典的问题，同时单链表可以采用数组实现，此时每个元素值作为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，则该题不可直接采用该方法。程序示例代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 |
#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;} |
效果如图：
取值为[1,n-1]含n个元素的整数数组，至少存在一个重复数，即可能存在多个重复数，O(n)时间内找出其中任意一个重复数，不使用额外存储空间。,布布扣,bubuko.com
取值为[1,n-1]含n个元素的整数数组，至少存在一个重复数，即可能存在多个重复数，O(n)时间内找出其中任意一个重复数，不使用额外存储空间。
原文：http://www.cnblogs.com/cysolo/p/3587466.html