问一个腾讯的算法题：有一个 vector 容器中，存有 1 亿个 qq 号（不重复），如何快速挑选出其中奇数号码？

[wind3110991]

如题，今年春季的笔试题，不知道腾讯想表达什么意思，自己不是很精通STL。
感觉直接遍历一遍然后考察vector[i]>>1;
如果奇数就提出来，算法开销O（n），不知道是不是有什么更好的方法？
大神勿喷，这题有没有必要用hash？

[jiang42]

听说腾讯有让做fib53的，我觉得。。。这题O(n)算法就行了？

[vibbow]

直接循环一遍，在内存里判断QQ号最后一位二进制是不是1？

[wind3110991]

@vibbow 我也觉得。。不知道他要表达什么了

[wind3110991]

@jiang42 fib53？斐波那契？

[xvsfezz]

内存够不够。。

[wy315700]

是不是不允许copy

[wind3110991]

@xvsfezz 假如不够呢，是不是hash到n个文件里？

[HanSonJ]

明天面试楼主才来问之前的问题…

[wind3110991]

@HanSonJ 今天看大数据时突然想起没有比较好的解决方案，身边同学也觉得题有问题，就搁浅了，你觉得怎么解决？

[wind3110991]

@wy315700 好像没提到

[HanSonJ]

@wind3110991 我是战斗力只有5的渣

[spacewander]

count += (v[i] & 1);
类似这样？
没用无重复的条件，但是O(n)加较小的常数因子，感觉没有比它更快了
再快就只能用并行算法了……

[acros]

考内存管理的效率吗？
qq号一亿个int，长度按4算，内存肯定不够一次载入。
另外还有vector内部内存模型问题吧，我需要复习下.....

[acros]

2了，现在qq号是11位以上了吧？存的string还是数值？

[jesse_luo]

@acros QQ 号好像有11 位了？ 所以按 64 位计算，8*100000000 Byte 约为 700 多 MB吧

可能要考虑 QQ 号数据动态变化，能多次迅速计算？

[acros]

@jesse_luo 怀疑int够不够....好像需要收集很多前置条件

[acros]

@jesse_luo 估计考官第一条审批还是看有没区分64，32呢....

[jiang42]

@wind3110991 对啊。。。

[NCE]

11wei % 2

[lucifer9]

给所有qq在线用户弹窗：
今天是马化腾的生日，挑出以下所有的偶数号码并回复偶数号码的个数有机会点亮头像哦

然后每个用户发10个号码，正好用上号码不重复的条件
运气好的话一遍就出来结果了

[cheng007]

有一个１亿的vector，说明内存不是问题，要拿出所有的奇数，必须完成一次遍历也就是O(n)，这题目应该是考并发吧，开多个线程每个线程负责一个段数据。

[wibile]

@lucifer9 你是个人才！请收下我的膝盖。ps，运气不好咋办。。。

[zwzmzd]

我记得题目是删除qq号

不过意思一样，用remove_if，原理类似于partition

[sigarron]

@spacewander 这哥们貌似对的，位运算总是最快的，但是vector的意义是啥呢？存储的是int64还是string呢？这些问题都值得考虑下。

[lucifer9]

@wibile 用户基数在那摆着呢，运气再不好也不至于需要1亿次吧

[xinyewdz]

普通的qq号是9位，大概就是1亿个。这数组不是稀疏数组，遍历一遍标注每个数组（用0和1标注）。然后直接输出下标是奇数并且值是1的。

[ybh37]

字符串和数字无所谓，只判断二进制的最后一位是不是0就可以了。

[imn1]

@ybh37 +1

[ugvfpdcuwfnh]

拆半查找都可以吧，2的27次方大于一亿。

前几次是外部排序，后面就是内部排序。

[lijinma]

@ugvfpdcuwfnh 还要排序？排序那就更复杂了

[ugvfpdcuwfnh]

@lijinma 不是排序，本身就是排好的，应该是外部查找和内部查找。

[ugvfpdcuwfnh]

哎？我突然发现我没看清题目，是要选出奇数号，我以为是从一亿号里选出一个号。

好吧，我楼上的回复都无视吧.....

[zcljy]

@ybh37 re

[ether]

map reduce!

[yuankui]

把奇数插入到首部,吧偶数插入到尾部
要取奇数的话,就循环从首部取完,直到遇到偶数...
要取偶数的化,就循环从尾部取,直到遇到奇数...

[yuankui]

我靠,如果有这种需求,为什么不用两个vector存储?

[yuankui]

你可以直接跟面试官说,你们这个前提很没水平

[sage417]

我觉得考的是大数据，跟技术还是偶数没什么关系，应该是map-reduce

[sen506]

2个迭代器A B
当当前数位奇数时*A++ = *B++；
当当前数为偶数时++B;
B到达容器结尾时结束;
最后vector.erase(A, vector.end());

应该就这样了吧。。

[laotaitai]

拿Python, 3秒就能把1亿个QQ遍历完

[also24]

看到中间越看感觉越奇怪……
返回头又看一遍才反应过来是 奇数 不是 质数 的我面壁去了……

(:o 」∠)_

[quericy]

@lucifer9 然后有用户手滑的,有无聊随便选的,还有好奇心害死猫觉得有隐藏条件然后全点一遍的23333

[blank4me]

@quericy 一组数据不要发给一个人撒。多发几个人看看，再判断是否相信他们的结果。就和reCAPTCHA一样。

[luoqeng]

vector<bool> == Bitmap
http://blog.csdn.net/u014082714/article/details/45022567

[khan]

判断低 bit位是否为1

[khan]

8byte int_64 * 100,000,000L 需内存约 100M

位运算 比 / %都要省 cpu, 剩下的内存问题可以多段分块加载

[khan]

体死早. 800M 内存 换成字符串大概不过2G, 加上指针 和 字符串本身内存, 分块处理 合并不可少

[wind3110991]

@khan 谢谢你的解答！我再想想，有点不理解