首页 > 试题广场 >

在10亿个unsigned int数中，如何判断一个给定的数

[问答题]
在10亿个unsigned int数中，如何判断一个给定的数是不是在其中？
添加回答
lixxxxxx头像 lixxxxxx
把10亿个数中的每一个用32位的二进制来表示。假设这10亿个数开始放在一个文件中。
 然后将这10亿个数分成两类:
      1.最高位为0
      2.最高位为1
    并将这两类分别写入到两个文件中，其中一个文件中数的个数<=5亿，而另一个>=5亿（这相当于折半了）；
与要查找的数的最高位比较并接着进入相应的文件再查找
    再然后把这个文件为又分成两类:
      1.次最高位为0
      2.次最高位为1
    并将这两类分别写入到两个文件中，其中一个文件中数的个数<=2.5亿，而另一个>=2.5亿（这相当于折半了）；
    与要查找的数的次最高位比较并接着进入相应的文件再查找。
    .......
    以此类推，就可以找到了,而且时间复杂度为O(logn)。
发表于 2019-07-01 10:22:26 回复(0)
uiop112233头像 uiop112233
编辑于 2023-12-23 16:28:22 回复(0)
我是好人x头像 我是好人x
bitmap
发表于 2020-03-21 18:06:20 回复(0)
游戏锦鲤-桃头像 游戏锦鲤-桃
十亿个数，2的31次方大概是21亿，可以装下所有的数。所以申请2的31次方个位覆盖这十亿个数，然后存在的数上的位为1，不存在为0，然后依次进行比较。所以大概内存占用2的28次方个字节=256MB。
发表于 2019-11-27 09:24:34 回复(0)
OnePiece201909200842439头像 OnePiece201909200842439
可以将1千个数为一行整成一个文本文件，将数据用spark读取，根据给定的数过滤判断该数是否在该行中，最后根据是否留有数据来判断，该数是否在其中。
发表于 2019-09-20 09:57:39 回复(0)
小余1头像 小余1
二分查找法
发表于 2019-08-16 15:44:24 回复(0)
清清兀商头像 清清兀商
int i;
List unsigned  = new  ArrayList();
for( i:unsigned){
    
}
发表于 2019-07-15 10:38:02 回复(0)
提交观点

问题信息

iHandy 算法工程师 2019 大数据开发工程师
上传者：小小
难度：
7条回答 1565浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号