/*
題目：一個(gè)數(shù)組，下標(biāo)從0到n，元素為從0到n的整數(shù)。判斷其中是否有重復(fù)元素
解題思路：循環(huán)遍歷數(shù)組中的每一個(gè)元素i，如果其值為-1，說明該元素已經(jīng)處理完畢。
否則，首先判斷其值是否與下標(biāo)一樣（a[i]==i），
如果不一樣，則將其值作為下標(biāo)（記t=a[a[i]]），判斷a[t]==-1,如果成立，則表示有重復(fù)的。
否則，令a[i]=a[t],a[t]=-1。表示新下標(biāo)t的元素已經(jīng)處理完畢。
再次判斷新的a[i]是否與下標(biāo)一樣...
詳細(xì)看代碼...
*/
#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
水 閱讀(3121)
評(píng)論(6) 編輯 收藏 引用 所屬分類:
算法與數(shù)據(jù)結(jié)構(gòu)