/*
题目：一个数组，下标从0到n，元素为从0到n的整数。判断其中是否有重复元素
解题思路：循环遍历数组中的每一个元素i，如果其值为-1，说明该元素已经处理完毕。
否则，首先判断其值是否与下标一样（a[i]==i），
如果不一样，则将其值作为下标（记t=a[a[i]]），判断a[t]==-1,如果成立，则表示有重复的。
否则，令a[i]=a[t],a[t]=-1。表示新下标t的元素已经处理完毕。
再次判断新的a[i]是否与下标一样...
详细看代码...
*/
#include "stdafx.h"
#include <iostream>
using namespace std;
//返回1表示有相同的，0表示没有
int HasSame(int a[], int n)
{
for (int i=0; i<=n; i++)
{
while (a[i] != i && a[i] != -1)
{
if (a[a[i]] == -1)
{
return 1;
}
a[i] = a[a[i]];
a[a[i]] = -1;
}
if (a[i] == i)
{
a[i] = -1;
}
}
return 0;
}
#define N 4
int _tmain(int argc, _TCHAR* argv[])
{
int a[N] = {0,2,3,3};
int iHasSame = HasSame(a, N);
cout<<iHasSame<<endl;
return 0;
}
posted on 2008-06-03 10:51
水 阅读(3123)
评论(6) 编辑 收藏 引用 所属分类:
算法与数据结构