人人网笔试题一道，小菜求解

cjaizss

已有的数是10,11,12,13,14,15,16,17,18
那么被抽掉的那个数是几啊?

cjaizss

int func(int a[9],int r[2])
{
       int min,max,i;
       long long sum;
       sum=max=min=a[0];
       for(i=1;i<9;i++) {
              if(a[i]>max)max=a[i];
              if(a[i]<min)min=a[i];
              sum+=a[i];
       }
       if(max-min==9) {
               r[0] = (int)(sum-((long long)max+(long long) min)*5);
               r[1] = -1;
       } else {
               r[0]=max+1;
               r[1]=min-1;
       }
}
//r[0],r[1]如果是非负数,则是可能值

keytounix

回复 1# zz8880


    这个题目还涉及比较简单的

第一个

才10个，可以用 累加和 - 取走后的累加

第二个

直接采用二分法查找就可以了就可以

数列 a[1000000];
取走后数据形成的数列为
b[1000000-1];

L =0;
H=10000000;

第一次二分法，


若

a[H/2]==b[H/2]

则 取走的数据位于

[H/2,H]之间

若不等
则位于
[0，H/2]之间

答题思路就是这样

如此循环
二分法的时间复杂度 是多少？O(lgn)吗？

还有一种方法

就是一个一个比较咯

时间复杂度 O(n)


我能想到最好的方法就是这俩个了

fallening

xor 吧，可能符合面试官的胃口，显得自己很有水平。
当然，也可以选素数乘法，显得更有水平。

xfxfxy

----------------------------
哪位大哥给介绍下？不懂
xfxfxy 发表于 2011-11-24 15:50

    查了下资料，是不是这样搞？
   ［code］
    for (i = min; i < min+n; ++i)
          num ^= i;
    for (i = 0; i < n - 1; ++i)
        num ^= arr;[/code]
---------------------------但是有11楼说的问题呀，－－－

rejoice914

异或：
1、具有结合性，
A ^ B ^ C  = A ^(B ^C) =(A ^ B) ^C
2、异或自己等于0 ， 异或 0 等于 自己
A ^ A =0

SUM(N) :把数组的元素都异或一边，
SUM(N-1) : 把剩下的元素异或一次。

SUM(N-1) ^ X = SUM(N)

SUM(N-1) ^ X ^ SUM(N-1) = SUM(N) ^ SUM(N-1)

X = SUM(N) ^ SUM(N-1);


新手拙见。

btdm123

rejoice914 发表于 2012-08-04 01:06
异或：
1、具有结合性，
A ^ B ^ C  = A ^(B ^C) =(A ^ B) ^C

你这是交换，不是结合

btdm123

题目是给出了新数组，旧数组不知道，要你求少了什么数。1000万个数的大数组，只差一个数，难道人家搞两份？

btdm123

简单的方法就是搞一个临时数组，每次从源数组里取一个数n，如果它不在临时数组中，就考虑将n-1和n+1插入临时数组，如果它在临时数组中，就将它从临时数组中删掉。复杂度n^2ln(n)

btdm123

cjaizss 发表于 2011-11-24 16:24
int func(int a[9],int r[2])
{
       int min,max,i;

这个办法好，异或一下也就是o(n)