主题：第67次编程比赛题目
boxertony [专家分：23030] 发布于 2008-06-17 22:02:00
题目：找重复数
给定一个含有n个数的序列，这个序列中恰好有一个数出现两次，请你求出这个数。（假定其他的数都只有一个）
函数原型如下：
// array[] -- n个数的序列，取值范围为[-2^30, 2^30]
// n -- 数的个数，2<=n<=10^7
// id[] -- 你的id号
//【return】-- 出现两次的数
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id, ""); // 请把你的id号填入""中
}
判断标准：
（1）正确
（2）时间效率
（3）空间效率
（4）可读性
比赛时间：
2008年6月17日22：00 -- 2008年6月24日22：00
最后更新于：2008-06-18 09:22:00
回复列表 （共21个回复）
11 楼
a199561097 [专家分：0] 发布于 2008-06-22 18:16:00
kan kan
12 楼
fdasf [专家分：470] 发布于 2008-06-22 19:44:00
const long RT = 1e10;
long sort(long array[], long x, long y)
{
if(x == y)
return RT;
long i = x,j = y;
long tmp = array[i];
while(i <j)
{
while((tmp < array[j]) && (i <j))
j--;
if(i < j)
{
if(tmp == array[j])
return tmp;
else
array[i++] = array[j];
}
while((tmp >array[i]) && (i <j))
i++;
if(i < j)
{
if(tmp == array[i])
return tmp;
else
array[j--] = array[i];
}
}
array[i] = tmp;
long a = x < i ? sort(array, x, i-1) : RT;
long b = j < y ? sort(array, j+1, y) : RT;
return (a == RT) ? b : a;
}
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id, "fdasf"); // 请把你的id号填入""中
long x = sort(array, 0, n-1);
if(x != RT)
return x;
for(int i = 0;i < n-1;i++)
if(array[i] == array[i+1])
return array[i];
}
13 楼
ckeryradish [专家分：140] 发布于 2008-06-22 21:49:00
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define FIND_APPEAR_TIMES 2
struct AppearTimes
{
char Positive:4;
char Negative:4;
};
#define MAX_ABS_LONG_VALUE 0x7FFFFFFFL
#define MAX_WND_WIDTH (MAX_ABS_LONG_VALUE >> 3) // >> 2 == 512M; >> 3 == 256M
#define NOT_APPEAR_NUM (MAX_ABS_LONG_VALUE)
int comp(const void *p1, const void *p2)
{
return (*(long*)p1 - *(long*)p2);
}
long simpleFindDuplicate(long array[], long n)
{
qsort(array, n, sizeof(array[0]), comp);
long l = 0;
long lAppearTimes = 1;
for (l = n -1; l > 0; l--)
{
if (array[l] == array[l - 1])
{
lAppearTimes++;
if (FIND_APPEAR_TIMES == lAppearTimes)
{
return array[l];
}
}
}
return NOT_APPEAR_NUM;
}
long getArrayAbsMax(long array[], long n)
{
long lAbsMax = array[0];
long lCurNum = 0;
long l = 0;
for (l = 1; l < n; l++)
{
lCurNum = array[l];
if (0 > lCurNum && -lCurNum > lAbsMax)
{
lAbsMax = -lCurNum;
}
else if (0 <= lCurNum && lCurNum > lAbsMax)
{
lAbsMax = lCurNum;
}
}
return lAbsMax;
}
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id, "ckeryradish");
long lAbsMax = getArrayAbsMax(array, n);
if ((n + n * (log(n) / log(2.0))) < (double)lAbsMax)
{
return simpleFindDuplicate(array,n);
}
long lWndWidth = MAX_WND_WIDTH;
long lWndCounts = 1;
if (MAX_WND_WIDTH >= lAbsMax)
{
lWndWidth = lAbsMax + 1; // +1 for 0
}
else
{
// -1, for lAbsMax % MAX_WND_WIDTH == 0
lWndCounts = ((lAbsMax - 1) / MAX_WND_WIDTH) + 1;
}
long lBufLen = sizeof(struct AppearTimes) * (lWndWidth + 1);// +1 for index start from 0;
struct AppearTimes *pAllAppearTimes = (struct AppearTimes*)malloc(lBufLen);
if (NULL == pAllAppearTimes)
{
printf("malloc %ld bytes failed\n", lBufLen);
return NOT_APPEAR_NUM;
}
long lWndLeft = 0;
long lWndRight = 0;
long lChecked = 0;
for (long w = 0; w < lWndCounts; w++, lWndLeft += 1 + lWndWidth)
{
if (0 > lWndLeft)
{
free(pAllAppearTimes);
return NOT_APPEAR_NUM;
}
lWndRight = lWndLeft + lWndWidth;
if (0 >= lWndRight)
{
lWndRight = MAX_ABS_LONG_VALUE;
}
memset(pAllAppearTimes, 0x00, lBufLen);
for(long l = 0; l < n; l++)
{
long lCurNum = array[l];
long lIndex = 0;
if (0 <= lCurNum && lWndLeft <= lCurNum && lCurNum <= lWndRight)
{
lIndex = lCurNum - lWndLeft;
pAllAppearTimes[lIndex].Positive++;
if (FIND_APPEAR_TIMES == pAllAppearTimes[lIndex].Positive)
{
free(pAllAppearTimes);
return lCurNum;
}
lChecked ++;
if (n == lChecked)
{
free(pAllAppearTimes);
return NOT_APPEAR_NUM;
}
}
else if (0 > lCurNum)
{
long lAbs = -lCurNum;
if (lWndLeft <= lAbs && lAbs <= lWndRight)
{
lIndex = lAbs - lWndLeft;
pAllAppearTimes[lIndex].Negative++;
if (FIND_APPEAR_TIMES == pAllAppearTimes[lIndex].Negative)
{
free(pAllAppearTimes);
return lCurNum;
}
lChecked ++;
if (n == lChecked)
{
free(pAllAppearTimes);
return NOT_APPEAR_NUM;
}
}
}
}
}
free(pAllAppearTimes);
return NOT_APPEAR_NUM;
}
15 楼
路人甲08 [专家分：20] 发布于 2008-06-23 16:32:00
#include<iostream>
#include<map>
using namespace std;
map<long,bool> compare;
long FindDuplicate(long array[], long n, char id[])
{
bool a;
strcpy(id, "路人甲08"); // 请把你的id号填入""中
for (int i=0;i<n;i++) {
if (compare[array[i]]==0) compare[array[i]]=true;
else return array[i];
}
return 0;
}
void main()
{
int n,answer;
char id[9];
cin>>n;
long* input;
input =new long [n];
for (int i=0;i<n;i++)
cin>>input[i];
if ((answer=FindDuplicate(input,n,id))!=0) cout<<answer;
else cout<<"no"<<endl;
}
我不清楚格式要求，如果程序没找到重复的数字，程序会显示no。
16 楼
路人甲08 [专家分：20] 发布于 2008-06-23 17:07:00
#include<iostream>
#include<map>
using namespace std;
map<long,bool> compare;
bool zero=false;
long FindDuplicate(long array[], long n, char id[])
{
bool a;
strcpy(id, "路人甲08");
for (int i=0;i<n;i++) {
if (compare[array[i]]==false) compare[array[i]]=true;
else {
if (array[i]==0) zero=true;
return array[i];
}
}
return 0;
}
void main()
{
int n,answer;
char id[9];
cin>>n;
long* input;
input =new long [n];
for (int i=0;i<n;i++)
cin>>input[i];
if ((answer=FindDuplicate(input,n,id))!=0 || zero==true) cout<<answer<<endl;
else cout<<"no"<<endl;
}
上面发的代码有错误，重新发一次。程序找不到重复出现的数是会输出“no”的字样。
代码很短，没有什么算法上的东西，用了map。不知道会不会超时，静候结果了。
17 楼
hxw910 [专家分：600] 发布于 2008-06-24 18:03:00
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <string>
#include <windows.h>
using namespace std;
const long size = pow(10,7);
long FindDuplicate(long array[], long n, char id[]); //查找
void set(long array[]); ////分配值
int Compare(const void *elem1, const void *elem2) //排序参数
{
return *((int *)(elem1)) - *((int *)(elem2));
}
void main()
{
srand( (unsigned)time( NULL ) );
long *array = new long [size] ;
set(array);
SYSTEMTIME sys;
GetLocalTime( &sys );
printf( "排序前时间%02d:%02d:%02d.%03d\n",sys.wHour,sys.wMinute, sys.wSecond,sys.wMilliseconds);
qsort(array,size,sizeof(array[0]),Compare);
GetLocalTime( &sys );
printf( "排序完时间%02d:%02d:%02d.%03d\n",sys.wHour,sys.wMinute, sys.wSecond,sys.wMilliseconds);
char id[20];
long n;
n = FindDuplicate(array,size,id);
cout<<n<<endl;
GetLocalTime( &sys );
printf( "查找完时间%02d:%02d:%02d.%03d\n",sys.wHour,sys.wMinute, sys.wSecond,sys.wMilliseconds);
delete array;
}
void set(long array[])
{
long j = rand()%size; //随机出一个位置使分配为同一个值
cout<<"j:"<<j<<endl;
long k=2;
for(long i=0;i<size;i++) //为方便检查，对应位置的值只与位置差2，值的范围符合要求
{
if (i!=j)
{
array[i] = k;
k++;
}
else
{
j = -1;
array[i] = k;
}
}
}
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id, "hxw910"); // 请把你的id号填入""中
long t = array[0];
for(long i=1;i<n-1;i++)
{
if(t == array[i])
{
cout<<"i:"<<i<<endl;
return t;
}
else
{
t = array[i];
}
}
cout<<"无重复数"<<endl;
return -1;
}
18 楼
xinshangtou [专家分：0] 发布于 2008-06-24 19:47:00
//vs2005下做的.
#include <iostream>
#include <set>
#include <cassert>
#include <utility>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;
template <class Value,class CrashCon=set<Value> >
class SimpleHashTable
{
struct Elem{
Value value;
CrashCon* crash;
};
Elem *pTable;
int iLength;
public:
typedef int Ret;
enum{
SUCESS,CRASH,EMPTY=0xCCCCCCCC};
SimpleHashTable()
{}
SimpleHashTable(int n)
{
assert(n>0);
pTable = new Elem[n];
iLength = n;
memset(pTable,0xCC,sizeof(Elem)*n);
}
~SimpleHashTable()
{
for(int i=0;i<iLength;i++)
if(pTable[i].crash != (CrashCon *)EMPTY)
delete pTable[i].crash;
delete []pTable;
}
Ret Insert(Value v)
{
int iIndex = v%iLength;
if(pTable[iIndex].value == EMPTY)
{
pTable[iIndex].value = v;
return SUCESS;
}
else
{
if(pTable[iIndex].value == v)
return CRASH;
if(pTable[iIndex].crash == (CrashCon *)EMPTY)
pTable[iIndex].crash = new CrashCon;
pair<CrashCon::iterator,bool> ret = pTable[iIndex].crash->insert(v);
if(ret.second == false)
return CRASH;
else
return SUCESS;
}
}
};
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id,"xinshangtou"); // 请把你的id号填入""中
if(!(n>=2&&n<10000000))
{
cout<<"err:数组太长!"<<endl;
return 0xCCCCCCCC;
}
typedef SimpleHashTable<long> MyTable;
MyTable tb(n);
for(int i = 0;i < n;i++)
{
if(tb.Insert(array[i]) == MyTable::CRASH)
{
return array[i];
}
}
return 0xCCCCCCCC;
}
void main()
{
long s[10]={1,2,3,4,5,6,7,8,19,7};
char buf[255];
cout<<FindDuplicate(s,10,buf)<<endl;
cout<<buf<<endl;
}
19 楼
hyfl [专家分：200] 发布于 2008-06-24 21:10:00
用到的结构体
struct node{
long value;
node* next;
};
函数体
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id,"hyfl");
const APRIME=35851;
long result=0; //返回值
int index=0;
node* p;
node* pHead=new node[APRIME];
for(int j=0; j<APRIME; j++)
pHead[j].next=NULL;
for(j=0; j<n; j++)
{
index=array[j] % APRIME;
if(index<0)
index=-index;
p=pHead[index].next;
while(p!=NULL)
{
if(array[j]==p->value)
{
result=array[j];
return result;
}
p=p->next;
}
p=new node;
p->value=array[j];
p->next=pHead[index].next;
pHead[index].next=p;
}
//释放空间
for(j=0; j<APRIME; j++)
{
p=pHead[j].next;
while(p!=NULL)
{
pHead[j].next=p->next;
delete p;
p=pHead[j].next;
}
}
delete pHead;
}
20 楼
Noar [专家分：0] 发布于 2008-06-24 21:47:00
void ShellSort(long* lArray, long size)
{
long i, j, increment, temp;
increment = 3;
while( increment > 0 )
{
for( i=0; i < size; i++ )
{
j = i;
temp = lArray[i];
while( (j >= increment) && (lArray[j-increment] > temp) )
{
lArray[j] = lArray[j - increment];
j = j - increment;
}
lArray[j] = temp;
}
if( increment/2 != 0 )
{
increment = increment/2;
}
else if( increment == 1 )
{
increment = 0;
}
else
{
increment = 1;
}
}
}
long FindDuplicate(long* pArray, long lSize, char* pId)
{
long i = 0;
int nMod = lSize % 2;
strcpy(pId, "Noar");
ShellSort(pArray, lSize);
if (nMod == 0)
{
for (; i < lSize; i+=2)
{
if (pArray[i] == pArray[i+2] || pArray[i] == pArray[i+1] )
{
return pArray[i];
}
else if (pArray[i + 1] == pArray[i + 2])
{
return pArray[i + 1];
}
}
}
else
{
for (; i < lSize - 1; i+=2)
{
if (pArray[i] == pArray[i+2] || pArray[i] == pArray[i+1] )
{
return pArray[i];
}
else if (pArray[i + 1] == pArray[i + 2])
{
return pArray[i + 1];
}
}
if (pArray[i] == pArray[lSize - 1])
{
return pArray[i];
}
}
return -1;
}
我来回复
您所在位置：