主题：第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个回复）
沙发
scutdx2005 [专家分：0] 发布于 2008-06-20 10:44:00
// array[] -- n个数的序列，取值范围为[-2^30, 2^30]
// n -- 数的个数，2<=n<=10^7
// id[] -- 你的id号
//【return】-- 出现两次的数
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id, "scutdx2005"); // 请把你的id号填入""中
//初试化堆数组的大小
long heapSize=1024;
//堆增长速度
long inc=2;
//初始化堆
long* heap=(long *)malloc(heapSize*sizeof(long));
//左右指针
long* left=(long *)malloc(heapSize*sizeof(long));
long* right=(long *)malloc(heapSize*sizeof(long));
//堆的访问状态
char* flag=(char *)malloc(heapSize*sizeof(char));
//错误
if(heap==0||flag==0||left==0||right==0)
return -1;
//初始化元素
for(long k=0;k<heapSize;k++)
{
flag[k]=0;
left[k]=-1;
right[k]=-1;
}
//输入值，搜索指针和堆指针
long *curNum,searchPoint,heapPoint=0;
long *newHeap,*newLeft,*newRight;
char *newFlag;
for(curNum=array;;curNum++)
{
searchPoint=0;
for(;;)
{
//若堆空间不足，则重新申请空间
if(heapPoint>=heapSize-1)
{
heapSize*=inc;
newHeap=(long *)realloc(heap,heapSize*sizeof(long));
newLeft=(long *)realloc(left,heapSize*sizeof(long));
newRight=(long *)realloc(right,heapSize*sizeof(long));
newFlag=(char *)realloc(flag,heapSize*sizeof(char));
if(newHeap==0||newFlag==0||newLeft==0||newRight==0)
return -1;
heap=newHeap;
flag=newFlag;
left=newLeft;
right=newRight;
for(long k=heapSize/inc;k<heapSize;k++)
{
flag[k]=0;
left[k]=-1;
right[k]=-1;
}
}
//搜索指针指位置空缺，则增加元素
if(flag[searchPoint]==0)
{
heap[searchPoint]=*curNum;
flag[searchPoint]=1;
heapPoint++;
break;
}
//否则比较当前数字与搜索指针所指数字的大小
else if(*curNum<heap[searchPoint])
{
if(left[searchPoint]<0)
left[searchPoint]=heapPoint+1;
searchPoint=left[searchPoint];
}else if(*curNum>heap[searchPoint])
{
if(right[searchPoint]<0)
right[searchPoint]=heapPoint+1;
searchPoint=right[searchPoint];
}
//找到相同的两个数字，清空内存返回值
else
{
free(heap);
free(left);
free(right);
free(flag);
return *curNum;
}
}
}
return -1;
}
板凳
willzhanglala [专家分：1350] 发布于 2008-06-21 11:51:00
直接用hash_set了，，，
#include <hash_set>
using namespace stdext;
long FindDuplicate(long arr[], long n, char id[])
{
strcpy(id, "willzhanglala"); // 请把你的id号填入""中
hash_set<long> mySet;
for(int i =0; i < n; i ++)
{
if ( mySet.find(arr[i]) != mySet.end() )
return arr[i];
mySet.insert( arr[i] );
}
return 0;
}
3 楼
yclz [专家分：1520] 发布于 2008-06-21 19:45:00
首次参赛,献丑了.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INVALID_VALUE 1073741824 + 1 //2^30 + 1
long GetData(long* arr,int startPos, int endPos)
{
int i = startPos;
int j = endPos;
long ch = arr[startPos];
if(i + 1 == j)
{
if(ch == arr[j])
return ch;
else
return INVALID_VALUE;
}
while(i < j)
{
while(i < j)
{
if(arr[j] > ch)
--j;
else if(arr[j] == ch)
return ch;
else
break;
}
arr[i] = arr[j];
while(i < j)
{
if(arr[i] < ch)
++i;
else if(arr[i] == ch)
return ch;
else
break;
}
arr[j] = arr[i];
}
arr[j] = ch;
if(i > startPos + 1)
{
ch = GetData(arr, startPos, i - 1);
if(ch != INVALID_VALUE)
return ch;
}
if(endPos > i + 1)
{
ch = GetData(arr, i + 1, endPos);
if(ch != INVALID_VALUE)
return ch;
}
return INVALID_VALUE;
}
long FindDuplicate(long array[], long n, char id[])
{
int i = 0;
int j = 0;
strcpy(id, "yclz");
return GetData(array, 0, 9);
}
4 楼
wxfbbsid [专家分：0] 发布于 2008-06-21 23:38:00
提示网页找不到，结果重发了
5 楼
wxfbbsid [专家分：0] 发布于 2008-06-21 23:39:00
long FindDuplicate(long array[], long n, char id[])
{
/* strcpy(id, "IMI"); */
long k,k1,count;
count = n-1;
for(k=0;k<count;k++)
{
for(k1=k+1;k1<n;k1++)
{
/* printf("%ld - %ld\r\n", array[k], array[k1]);*/
if( array[k] == array[k1] )
return array[k];
}
}
}
6 楼
yuwgle [专家分：30] 发布于 2008-06-21 23:46:00
用哈希表处理，时间复杂度o(n),空间复杂度o(n)。
typedef struct _elem
{
_elem()
{
w=0;
count=0;
}
int w; //关键字
int count; //出现次数
}HASH;
HASH* hashtable;
int getW(long a)
{
int b;
b=a+97;
b/=6;
if (b==0)
{
b=a+37;
}
return b;
}
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id, "yuwg_le"); // 请把你的id号填入""中
hashtable = new HASH[n];
int i,j,w;
for (i=0;i<n;i++)
{
w = getW(array[i]);
j = array[i]%n;
j=j>=0?j:-j;
while (hashtable[j].w!=0)
{
if (hashtable[j].w == w)
{
return array[i];
}else
j = j / 7 * 5 + i/7*2; //解决冲突
}
hashtable[j].w = w;
hashtable[j].count++;
}
}
7 楼
飞镝鸣处 [专家分：0] 发布于 2008-06-22 01:52:00
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id, "飞镝鸣处");
bool a[2147483648];//我不知道应许不应许我开这么大的数组
for(long i=0;i<n;i++)
{
if ( a[1073741842+array[i]] )
return array[i];
a[1073741842+array[i]] =1;
}
}
9 楼
blue.lake [专家分：0] 发布于 2008-06-22 14:35:00
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
long FindDuplicate(long array[], long n, char id[])
{
strcpy(id, "blue.lake");
cout<<"My id is "<<id<<endl;
int x = 0;
for (int i = 0; i < n; i++)
{
x = array[i];
for (int j = i+1; j < n; j++)
{
if (x == array [j])
{
cout<<"the number \""<<x<<"\" has appear twice!"<<endl;
return x;
}
}
}
cout<<"None of the number has appear twice!"<<endl;
return -1;
}
main()
{
char id[] = "blue.lake";
string fileName;
cout<<"Input file's name:";
cin>>fileName; //输入你储存数据的文件名
ifstream readinFile(fileName.c_str());
if(!readinFile.good())
{
cout<<"ERROR!Input the wrong file's name!"<<endl;
return -1;
}
int i = 0;
long n = 0;
long *array = NULL;
while(readinFile>>i)
{
n++; //计算有多少个数据
}
array = new long[n]; //动态申请一个数组储存数据
readinFile.close();
ifstream readinFile2(fileName.c_str());
for (i = 0; i < n; i++)
{
readinFile2>>array[i]; //录入数据到数组array中
}
long x = FindDuplicate(array, n, id);
delete []array;
if (-1 != x)
{
return x;
}
else
{
return -1;
}
}
10 楼
廖增祥 [专家分：3930] 发布于 2008-06-22 16:59:00
[code=c]
// 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号填入""中
long i, j;
for(i = 0; i < n; i ++)
{
for(j = i + 1; j < n; j ++)
{
if(array[i] == array[j])
return array[i];
}
}
return -1;
}
[/code]
我来回复
您所在位置：