代码拉取完成,页面将自动刷新
同步操作将从 doocs/advanced-java 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给定 40 亿个不重复的没排过序的 unsigned int 型整数,然后再给定一个数,如何快速判断这个数是否在这 40 亿个整数当中?
依然可以用分治法解决,方法与前面类似,就不再次赘述了。
由于 unsigned int 数字的范围是 [0, 1 << 32)
,我们用 1<<32=4,294,967,296
个 bit 来表示每个数字。初始位均为 0,那么总共需要内存:4,294,967,296b≈512M。
我们读取这 40 亿个整数,将对应的 bit 设置为 1。接着读取要查询的数,查看相应位是否为 1,如果为 1 表示存在,如果为 0 表示不存在。
判断数字是否存在、判断数字是否重复的问题,位图法是一种非常高效的方法。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。