下面是思科的笔试题。
数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)
这道题的难点是“时间复杂度必须为o（N）”。
我没想出来怎么编写，大家试试看

倒。。。。。。如果不限制空间那就很简单啊，统计一下就行了
不过你没有说清楚有没有空间限制

直接放入大数组~呵呵

//下面是我的算法
void search(int N,int a[])
{
int i,flag;
for(i=0;i<N;i++)
{
flag=a[i]%N;
if(a[flag]<N)
a[flag]+=N;
else
printf("重复的数字为%3d/n",flag);
}
}
//算法没有最好只有更好,请多动脑,想出更好的

[此贴子已经被作者于2007-8-22 20:01:42编辑过]

4楼是我小弟写的，怎么样？
还是我教导有方啊！

/*---------------------------------------------------------------------------
File name: 一道思科的笔试题.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 8/22/2007 05:11:39
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

http://bbs.bc-cn.net/viewthread.php?tid=164597

一道思科的笔试题下面是思科的笔试题。
数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)
这道题的难点是“时间复杂度必须为o（N）”。
我没想出来怎么编写，大家试试看

Sample output:

4 6 19 15 17 7 0 18 12 10 14 5 16 8 1 3 9 2 13 11
4 6 19 15 17 7 0 18 12 10 14 5 16 8 1 3 9 2 13
The missing number is 11
Press any key to continue . . .

5 7 8 0 9 10 12 19 17 18 13 11 4 14 2 15 3 1 6 16
5 7 8 0 9 10 12 19 17 18 13 11 4 14 2 15 3 1 6
The missing number is 16
Press any key to continue . . .
*/

#include <iostream>
#include "hjns.h" // my namesapce file (you don't own it)

using namespace std;

/**
My random permutation algorithm.

You will not be able to run this.
*/
void randPerm(int* a, int n);

/** O(N) space + O(N) time algorithm. This algorithm
uses an extra flags buffer.
* @param a --- the int buffer
* @param n --- size of the buffer
* @return returns the the missing number
*/
int findMissingInt(int*a, int n);

/** O(1) space + O(N) time algorithm. This algorithm
calculates the sum of 1+2+...N, so that N*(N+1)/2 has
to be less than INT_MAX. In other words, this works for
small N.
* @param a --- the int buffer
* @param n --- size of the buffer
* @return returns the the missing number
*/
int findMissingInt2(int*a, int n);

/** O(1) space + O(N) time algorithm. Use the properties
of exclusive or (the ^ operator). This is one of the
best algorithms.
* @param a --- the int buffer
* @param n --- size of the buffer
* @return returns the the missing number
*/
int findMissingInt3(int*a, int n);

int main()
{
const int kSize = 20;
int a[kSize];
randPerm(a, kSize);
hj::print(a, kSize);
hj::print(a, kSize-1);
cout<<"The missing number is "<<findMissingInt(a, kSize-1)<<endl;

return 0;
}

void randPerm(int* a, int n)
{
int i;
for(i=0; i<n; ++i)
a[i] = i;

hj::number::random rd;

for(i=1; i<n; ++i)
hj::swap(a[i], a[rd(0, i)]);

}

int findMissingInt(int*a, int n)
{
int* b =new int[n+1];
int i;

memset(b, 0, (n+1)*sizeof(int));
//for(i=0; i<=n; ++i)
// b[i] = 0;

for(i=0; i<n; ++i)
b[a[i]] = 1;

for(i=0; i<=n; ++i)
if( b[i] == 0 )
return i;

delete [] b;

return -1;
}

int findMissingInt2(int*a, int n)
{
int i;
int sum=0;

for(i=0; i<n; ++i)
{
sum+=(-a[i]+i+1);
}

return sum;
}

int findMissingInt3(int*a, int n)
{
int res = 0;
int i;

for( i=0; i<n; ++i)
res ^= a[i];

for(i =0; i<=n; ++i)
res ^= i;

return res;
}

HJin没有看清题目意思，要求是找出重复的，不是缺失的。the reduplicate not the missing!


findMissingInt最简单容易想到，findMissingInt3思想类似于findMissingInt2，但用了两个循环。findMissingInt2最好，考虑异或运算相对于加减运算执行速度快findMissingInt3其次。

/*---------------------------------------------------------------------------
File name: findMissingAndDuplicate.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 8/22/2007 10:48:40
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------
http://bbs.bc-cn.net/viewthread.php?tid=164597

下面是思科的笔试题。
数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)
这道题的难点是“时间复杂度必须为o（N）”。
我没想出来怎么编写，大家试试看

Sample output:
---------------------------------------------------------------------------
6 18 1 5 11 13 2 12 15 9 16 20 4 17 19 10 7 14 8 3
6 18 1 5 11 3 2 12 15 9 16 20 4 17 19 10 7 14 8 3
The duplciate number is 3
The duplciate number is 3
The missing number is 13
Press any key to continue . . .

1 14 15 10 19 17 11 3 12 5 2 20 8 9 4 7 13 18 16 6
6 14 15 10 19 17 11 3 12 5 2 20 8 9 4 7 13 18 16 6
The duplciate number is 6
The duplciate number is 6
The missing number is 1
Press any key to continue . . .

*/

#include <iostream>
#include "hjns.h"
using namespace std;

/** O(n) space + O(n) time. Find only the duplicate
* number.
*
* @param a --- the int buffer
* @param n --- size of the buffer
* @param missingNumber --- the missing number
* @return returns the duplicate number.
*/
int do_dup(int a[], int n);

/** O(n) space + O(n) time. Find both the duplicate
* number and the missing number.
*
* @param a --- the int buffer
* @param n --- size of the buffer
* @param missingNumber --- the missing number
* @return returns the duplicate number.
*/
int findDuplicatesAndMissing(int*a, int n, int& missingNumber);

int main()
{
const int kSize = 20;
int a[kSize];
int missingNumber;
int dupIndex;
int duplicate;

// generate a valid input:
// a[kSize-1] is one of the two duplicates
hj::number::randPerm(a, kSize);
hj::print(a, kSize);

hj::number::random rd;
dupIndex = rd(0, kSize-2);
a[dupIndex] = a[kSize-1];
hj::print(a, kSize);

cout<<"The duplciate number is "<<do_dup(a, kSize)<<endl;

duplicate = findDuplicatesAndMissing(a, kSize, missingNumber);
cout<<"The duplciate number is "<<duplicate<<endl;
cout<<"The missing number is "<<missingNumber<<endl;

return 0;
}

int do_dup(int a[], int n)
{
int *b;
int i;

b = new int[n+1];
memset(b, 0, (n+1)*sizeof(int));

for(i=0; i<n; ++i)
++b[a[i]];

for(i=1; i<=n; ++i)
{
if(b[i]==2)
break;
}

delete [] b;

return i;
}

int findDuplicatesAndMissing(int*a, int n, int& missingNumber)
{
int *b;
int i;
int dup;

b = new int[n+1];
memset(b, 0, (n+1)*sizeof(int));

for(i=0; i<n; ++i)
++b[a[i]];

for(i=1; i<=n; ++i)
{
if(b[i]==2)
dup = i;
else if(b[i]==0)
missingNumber = i;
}

delete [] b;

return dup;
}

ls你贴这样多是怎么贴的呀，在编译器做的然后拷贝么？

[此贴子已经被作者于2007-8-23 8:35:28编辑过]

我说明一下：只需要而且仅要求用一个函数！再次，算法复杂度O(N)!
像HJin就不符合笔试的要求