<分区>
我遇到了这个面试问题,我试图了解如何解决这个问题。我读了this关于SO的问题。我理解帖子作者的方法,但是我不理解接受的答案中建议的方法。所以我搬到了这个blog .根据这篇博客,我们可以计算出每个位位置上的 0 和 1 的数量,并从中找出缺失的数字。但是为此,文件应该有 2^32-1 个大于 40 亿的数字。那么这种方法应该行不通吧?我确定我的理解有问题,但我无法找出缺失的链接。
<分区>
我遇到了这个面试问题,我试图了解如何解决这个问题。我读了this关于SO的问题。我理解帖子作者的方法,但是我不理解接受的答案中建议的方法。所以我搬到了这个blog .根据这篇博客,我们可以计算出每个位位置上的 0 和 1 的数量,并从中找出缺失的数字。但是为此,文件应该有 2^32-1 个大于 40 亿的数字。那么这种方法应该行不通吧?我确定我的理解有问题,但我无法找出缺失的链接。
最佳答案
如果您有一个从 0 到 2^N-1 的“完整”数字序列,那么每个位位置中设置的位数将相等(并且等于 (2^N)/2)。
如果只少一个数,那么它的1位对应的是短一位数的位。
请注意,这仅适用于 2 的幂,但可能可以为“奇数”计算出更复杂的公式。
关于java - 给定 40 亿个未排序的整数,寻找缺失的整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22774896/
相关文章:
java - 创新设置: How to install a file after install?
c++ - 在给定时间内将频率从 f1 缓慢上升到 f2 的正弦波
delphi - 分配一种类型的指针并将其作为不同类型但大小相同的指针进行处理可以吗?
java - Spring 将 ModelMap 模型属性传递给 JSP
java - 是否可以将 List<Key> 作为实体的属性存储在 Google App Engine (GAE) 中?
algorithm - 我们可以在小于 O(n*n) ...( nlogn 或 n) 的时间内计算吗