问一个腾讯的算法题:有一个 vector 容器中,存有 1 亿个 qq 号(不重复),如何快速挑选出其中奇数号码?

2015-04-07 22:22:37 +08:00
 wind3110991

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

5275 次点击
所在节点    C
48 条回复
cheng007
2015-04-08 09:17:30 +08:00
有一个1亿的vector,说明内存不是问题,要拿出所有的奇数,必须完成一次遍历也就是O(n),这题目应该是考并发吧,开多个线程每个线程负责一个段数据。
wibile
2015-04-08 09:20:06 +08:00
@lucifer9 你是个人才!请收下我的膝盖。ps,运气不好咋办。。。
zwzmzd
2015-04-08 09:21:26 +08:00
我记得题目是删除qq号

不过意思一样,用remove_if,原理类似于partition
sigarron
2015-04-08 09:32:23 +08:00
@spacewander 这哥们貌似对的,位运算总是最快的,但是vector的意义是啥呢?存储的是int64还是string呢?这些问题都值得考虑下。
lucifer9
2015-04-08 09:49:39 +08:00
@wibile 用户基数在那摆着呢,运气再不好也不至于需要1亿次吧
xinyewdz
2015-04-08 09:59:34 +08:00
普通的qq号是9位,大概就是1亿个。这数组不是稀疏数组,遍历一遍标注每个数组(用0和1标注)。然后直接输出下标是奇数并且值是1的。
ybh37
2015-04-08 10:06:53 +08:00
字符串和数字无所谓,只判断二进制的最后一位是不是0就可以了。
imn1
2015-04-08 10:18:52 +08:00
@ybh37 +1
ugvfpdcuwfnh
2015-04-08 12:30:02 +08:00
拆半查找都可以吧,2的27次方大于一亿。

前几次是外部排序,后面就是内部排序。
lijinma
2015-04-08 13:22:49 +08:00
@ugvfpdcuwfnh 还要排序?排序那就更复杂了
ugvfpdcuwfnh
2015-04-08 13:56:29 +08:00
@lijinma 不是排序,本身就是排好的,应该是外部查找和内部查找。
ugvfpdcuwfnh
2015-04-08 13:58:57 +08:00
哎?我突然发现我没看清题目,是要选出奇数号,我以为是从一亿号里选出一个号。

好吧,我楼上的回复都无视吧.....
zcljy
2015-04-08 14:01:26 +08:00
@ybh37 re
ether
2015-04-08 14:14:05 +08:00
map reduce!
yuankui
2015-04-08 14:27:35 +08:00
把奇数插入到首部,吧偶数插入到尾部
要取奇数的话,就循环从首部取完,直到遇到偶数...
要取偶数的化,就循环从尾部取,直到遇到奇数...
yuankui
2015-04-08 14:41:34 +08:00
我靠,如果有这种需求,为什么不用两个vector存储?
yuankui
2015-04-08 14:42:02 +08:00
你可以直接跟面试官说,你们这个前提很没水平
sage417
2015-04-08 16:10:23 +08:00
我觉得考的是大数据,跟技术还是偶数没什么关系,应该是map-reduce
sen506
2015-04-08 16:42:18 +08:00
2个迭代器A B
当当前数位奇数时*A++ = *B++;
当当前数为偶数时++B;
B到达容器结尾时结束;
最后vector.erase(A, vector.end());

应该就这样了吧。。
laotaitai
2015-04-08 17:12:11 +08:00
拿Python, 3秒就能把1亿个QQ遍历完

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/182211

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX