没有合适的资源?快使用搜索试试~ 我知道了~
40亿个非负整数中找到未出现的数
1 下载量 119 浏览量
2021-01-07
12:49:59
上传
评论
收藏 46KB PDF 举报
温馨提示
试读
1页
32位无符号整数的范围是0 ~ 4 294 967 295,现在有一个正好包含40亿个无符号整数的文件,所以在整个范围中必然有未出现过的数。怎么找到所有未出现过的数? 要求: 可以使用最多1GB的内存。 进阶: 内存限制10MB,但是只用找到一个没出现过的数即可。 常规方法:假设用哈希表来保存出现过的数,那么如果40亿个数都不同,则哈希表的记录数为40亿条,存一个32位整数需要4B,所以最差情况下需要40亿×4B = 160亿字节,大约需要16GB的空间,不符合要求。 思路: ① 使用bit map的方式来表示数出现的情况,申请一个长度为4 294 967 295的 bit 类型的数组 bit
资源推荐
资源评论
资源评论
weixin_38621427
- 粉丝: 10
- 资源: 941
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功