登录
  • #刷题
  • #careercup

讨论一下10.3

sally216
774
0
题意是一个文件里面有1G的不重复的非负整数,只有10M的内存,找出一个不在文件里

面的非负整数。

解法和他一样,划分区间再统计,但是智商拙计没有看懂他后面对区间大小的推导。。。

我是这样分的,[0, 1000), [1000, 2000)....,这样的话最多只要1M的区间。10M的内[/size]

存可以开2.5M的整型数组了,所以开一个1M的数组,扫一遍文件记录每个区间里面数字

出现的次数。然后再找到一个计数小于1000的区间,再扫一遍文件,找出那1000个数当

中没有出现的(这一步目标只有1000个数,内存很小)。

搞不懂他最后为啥还要用bit vector。。是不是我算错了。。
0条回复
热度排序

发表回复