[IT码农相关]来道高端的面试题
- mirokuneal今天看见一道题，令我叹为观止
第一问：（这个是经典题，相信不少人都会）
一个数组，其中只有一个数出现了一次，另外其他数均出现两次，请找出这个出现一次的数， 要求O(n)的时间复杂度和O(1)的空间复杂度
比如：输入[2, 2, 3, 4, 3, 1, 4] 输出 1
第二问，这个就高端了： （注意是这一问高端）
一个数组，其中只有一个数出现了一次，另外其他数均出现三次，请找出这个出现一次的数， 要求O(n)的时间复杂度和O(1)的空间复杂度
比如：输入[2, 3， 2, 4, 2, 3, 3] 输出 4
[本帖最后由 mirokuneal 于 2011-3-18 03:52 编辑] - 分不清雨水泪水这题都快考烂了。。。。
请看《编程之美》一书 - 788414这个不难...
- sectionboy谁来看看这是干嘛的:D
cwd
xor ax,dx
sub ax,dx
[本帖最后由 sectionboy 于 2011-3-16 13:02 编辑] - 子山这是入门级
楼主你太嫩了，挨踢行业不适合你 - 分不清雨水泪水通常解法是利用hashtable,伪码：
for ( i : arr ){
if( hash表中存在此元素)
从hash表中删除此元素
else
将此元素放入hash
}
一趟循环处理完后，hash表应该只有一个元素，就是那个出现一次的数，输出即可
附加问题同理，处理一下hash判断部分即可
BTW:这不是最优解 - 死命遭唤我怎么记得在沙特那个人写的书里有这种问题得解法。。
- 保密頭像不錯, 順便問最優解.
- Crusher+65535
- leonWongposted by wap
这题高端在什么地方啊？ - zhangu2就是个考hash table或hash map的东西，都烂大街了。。。
- 分不清雨水泪水最优解4L贴了，用异或，相同的数字异或完为0，所以所有数组中的数字异或的结果就是那个只出现一次的数
- mirokuneal楼上都是神
关键是第二个问题，o(n)时间， o(1)常数空间怎么做？
本帖最后由 mirokuneal 于 2011-3-16 13:31 通过手机版编辑 - hailfruhner.......................
- 离神最近的人这个牛逼，没想到
第二个怎么做？
[本帖最后由 离神最近的人 于 2011-3-16 14:24 编辑] - Eclipses传统做法是6楼说的，不过如果先对数组排序后遍历会不会效率高点》？
- 神之一技异或一把就行
- ffcactus想了一会， 还是不明白， 什么叫“所有数组中的数字异或”？
- fuckmic如果输入有误呢？不考虑容错吗？
- mirokuneal我擦，你这个复杂度太高了，还不如直接sort
- mirokuneal这题高端就高端在第二问
一堆人看到第一问就高潮了(第一问确实是经典题），直接忽视第二问，实在不知道说什么好
给个第二问的答案吧：复制内容到剪贴板[本帖最后由 mirokuneal 于 2011-3-18 03:54 编辑]代码:
int main(){
int B[] = {1,1,1,3,3,3,20,4,4,4};
int ones = 0 ;
int twos = 0 ;
int not_threes;
int x,i ;
for( i=0; i< 10; i++ )
{ x = B;
twos |= ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}
printf("\n unique element = %d \n", ones ); return 0;
} - voidstar各种与 或 异或
- nintenyun复制内容到剪贴板[本帖最后由 nintenyun 于 2011-3-18 13:01 编辑]
代码:
- 阿弄oracle數據庫表示沒難度
--set serveroutput OFF
declare
v_return varchar2(10000):='2,3,2,4,2,3,3';
v_b number;
i number:=1;
begin
v_return:=','||v_return||',';
loop
select instr(v_return,','||substr(v_return,instr(v_return,',',1,i)+1,instr(v_return,',',1,i+1)-instr(v_return,',',1,i)-1)||',',1,2)
into v_b from dual;
if v_b=0 then
dbms_output.put_line('test='||substr(v_return,instr(v_return,',',1,i)+1,instr(v_return,',',1,i+1)-instr(v_return,',',1,i)-1));
exit;
end if;
i:=i+1;
end loop;
end; - 阿弄如果是表中的一列數就更容易
declare
v_return varchar2(100);
begin
select a
into v_return
from x_table group by a having sum(1)=1;--
dbms_output.put_line('test='||v_return);
end; - hourousha我觉得挺有难度，因为你得证明这个方法的时间复杂度是O(n)，而空间复杂度是O(1)……
- 流浪的枪骑兵惭愧，没能看懂，能否注释一下？
- 阿弄我并不是程序员，只不过因为职业缘故经常需要看或者写PLSQL代码，看你字面的意思是有更高效率的写法，那么请教了
- mirokuneal主要问题是SQL的每次查询不是O(1)的时间复杂度
- bwl3b说白了，第一、二问以及类似的第 X 问解法是通的
MN+1 个数，N 个数出现 M 次，1 个数出现 1 次
则任意以一种 K 进制（要求 K<=M）表达这些数、并作不进位加法之后，各位上的结果分别 mod M 就完事
你看不懂的这段代码，是以 2 进制表示数，做不进位加法，每个位上只保留 mod 3 的结果
这种属于一通百通的量产面试题……
[本帖最后由 bwl3b 于 2011-3-19 01:59 编辑] - eos我想知道列出从1到一千亿里所有的质数这个程序咋编
- mirokuneal是以 2 进制表示数，做不进位加法，每个位上只保留 mod K 的结果
这个有通用解法么？ - mirokuneal基本原理是ones里面存出现过一次数的bit位（出现2次的会被异或掉）
twos里面存bit出现过两次数的位（x与上ones的结果，就是出现两次的bit位，加入twos里面）
当ones和twos里面相同位都为1时，说明这个bit位出现了3次
把这些bit位从ones和twos里面剔除
最后ones里面就是仅仅出现过一次的bit位，就是最后结果 - bwl3b是 mod M，不是 mod K……
如果 M 固定（而非输入的参数），可以像上面这个同学一样手动实现“在线的”二进制加法和取模操作
实际上空间效率是 O(log(M))，时间效率是 O(L*log(M))（L=N*M+1，即输入数据数的个数）
因为 M 固定，所以看起来是 O(1)::O(L)
如果 M 不固定，分三种情况
1. 知道 N 的范围即 N<=NN，那么可以手动实现“在线”二进制加法、全部输入完毕后再统一取模，效率是 O(log(NN))::O(L*log(NN))
2. 不知道 N 的范围，但知道 M 的范围即 M<=MM，此时需要蛋疼的高端人士手动实现“在线的”二进制加法和取模，如果能实现，效率是 O(log(MM))::O(L*log(MM))
3. 通用的慢解法，需要知道所有数的范围（即最大值不超过 H），此时令 K=M（此前 K 一直等于 2），把每个输入的数都转化到 M 进制下，轻松实现“在线”加法（不需要搞取模操作了），效率是 O(log(H))::O(L*log(H)) - 离神最近的人半懂，求详细资料
不进位加法，二进制下不就是将两数异或么；然后逐位对M取模，在K（进制）<M的情况下，每位都不变。那按你的说法，岂不是全部异或一遍就OK了？貌似不对啊
[本帖最后由 离神最近的人 于 2011-3-19 10:16 编辑] - bwl3b加法
[0,1]+[0,1]=[1,0]
异或
[0,1]+[0,1]=[0,0]
不进位加法
[0,1]+[0,1]=[0,2]
这个“2”怎么表示呢？
在上面那个同学的程序里，是用一个两位二进制数 [two_i,one_i] 来表示的，这里 two_i 是他那个变量 twos 的对应二进制位
同时这个同学做了在线的 mod 3 操作（就是每加完一次就通过调整 twos ones 做 mod 3）
举个直观的例子，输入为 {1,1,3,3,1,3,2,7,7,7}
二进制视角为 [0,0,1]*3,[0,1,1]*3,[1,1,1]*3,[0,1,0]*1
全部加起来为 [3,7,9]
每个位对 M=3 取模 [0,1,0]
于是得到“2” - 离神最近的人原来你的“不进位加法”是这个意思，理解错了
- mirokuneal关键是怎么用代码实现？