取值为[1,n-1]含n个元素的整数数组，至少存在一个重复数，即可能存在多个重复数，O(n)时间内找出其中任意一个重复数，不使用额外存储空间。

有一种非常诡异的算法，就是采用类似于单链表是否存在环的问题。“判断单链表是否存在环”是一个非常经典的问题，同时单链表可以采用数组实现，此时每个元素值作为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;

}

　　效果如图：

巴特西

取值为[1,n-1]含n个元素的整数数组，至少存在一个重复数，即可能存在多个重复数，O(n)时间内找出其中任意一个重复数，不使用额外存储空间。

最新文章

热门文章