面试时碰到的一个算法，求高人解答

2013-10-14

面试时遇到的一个算法，求高人解答。前天去兴业银行面试，有问到一个题目：a[N]存放了N个整形数，其中有两个重

面试时遇到的一个算法，求高人解答。
前天去兴业银行面试，有问到一个题目：a[N]存放了N个整形数，其中有两个重复找出重复的数字，要求时间复杂度为O(n).
我的思路是这样的,1，先找出a[N]中最大的数MAX
2，然后定义一个数组b[MAX],并对其赋初值0.
3，从0到i-1，执行b[a[i]]++,判断（b[a[i]]==2）？返回值i。

其实自己想想都很荒唐，MAX有多大谁知道呢。有思路的说下，求助。

PS：10年毕业，做了一年多的码农，写一些没逻辑的C代码，现在还是菜鸟一个。前途迷茫啊。
[解决办法]

引用:

引用:
前天去兴业银行面试，有问到一个题目：a[N]存放了N个整形数，其中有两个重复找出重复的数字，要求时间复杂度为O(n).
我的思路是这样的,1，先找出a[N]中最大的数MAX
2，然后定义一个数组b[MAX],并对其赋初值0.
3，从0到i-1，执行b[a[i]]++,判断（b[a[i]]……

错了，确实你那样写，在知道最大的数MAX，用1L说的map可以
[解决办法]
把MAX定义为OXFFFFFFFF就可以了，反正只考虑时间不考虑空间
[解决办法]

引用:

引用:
题没出完整吧

额，我也感觉是这样子，大概就是那样。可能主要是考个思路吧。

2.数组a[N]，存放了1至N-1个数，其中某个数重复一次。写一个函数，找出被重复的数字.时间复杂度必须为o（N）函数原型：
int do_dup(int a[],int N)
答:int do_dup(int a[],int N)    //未经调试
{
      int sun = 0;
      int sum2;
      for(int i=0;i<N;++i)
      {
        Sum+=a[i];
      }
      Sum2 = (1+N-1)*N/2;
      Return (sum-sum2);
}

来自http://mazhijing.blog.51cto.com/215535/68640
[解决办法]


/*
可以用位图做的，这个位图可以用int数组。但要将某一个数字对应到数组中的某一位，
而不是对应某一个int，这样可以大量节省空间。鉴于可能有负数所以要将所有的数字
加上32位可以表示的最大的整数（ox7fffffff)/32，然后再定位到相应的bit。
粗略的计算需要的空间为：
4*1024*1024*1024（bit)/8(bit)/1024(Byte)/1024(K)=512M.
所以一般机器是可以胜任的。

  可以参考下面算法。
*/
#include<iostream>
using namespace std;
const int MAX=0x7fffffff;
const int A=32;
const int B=MAX/32+1;
const int C=5;
const int MASK=0x1f;
int *bits=new int[(MAX/32+1)*2];

void set(int i){
int pos=B+(i>>C);
bits[pos]
[解决办法]
=1<<(i&MASK);
cout<<"num :"<<i<<" pos :"<<pos<<" -> offset"<<(i&MASK)<<endl;
}

bool test(int i){
int pos=B+(i>>C);
return bits[pos]&(1<<(i&MASK));
}

int main(){
memset(bits,0,(MAX/32+1)*2*4);
int a[]={0x80000000,0x80000000+1,0,0x7fffffff,0x7ffffffe,0};
for(int i=0;i<sizeof(a)/4;++i){
cout<<test(a[i])<<endl;
set(a[i]);
cout<<"-------------"<<endl;
}


return 0;
}

热点排行

C语言

面试时碰到的一个算法，求高人解答