gpt4 book ai didi

algorithm - 编程珍珠 : Finding the missing integer in a file of 4 billion integers

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:07:48 25 4
gpt4 key购买 nike

问题:输入在顺序文件中。该文件最多包含 40 亿个整数。查找缺失的整数。

解决方案据我理解:

  1. 制作两个临时文件,一个以0开头,一个以1开头

  2. 两个MUST之一(4.3B鸽子洞和4B鸽子)小于2B。选择文件并在第 2 位重复步骤 1 和 2,然后在第 3 位等等。

本次迭代的结束条件是什么?

此外,书中提到算法的效率为 O(n)但是,

第 1 次迭代 => n 个探测操作
第二次迭代 => n/2 次探测操作
.
.
.
n + n/2 + n/4 +... 1 => nlogn??

我错过了什么吗?

最佳答案

您将检查这两个文件并选择元素最少的文件。

您将重复该过程,直到您完成所有 32 位,最后您将拥有一个文件 0 元素。这是其中一个丢失的数字应该在的地方。因此,如果您一直在跟踪到目前为止过滤的位,您就会知道数字应该是多少。

请注意,这是查找一个(即“任何”)缺失的数字。如果给定一个包含 40 亿(不是 2^32 (4294967296))个整数的(无序)序列列表,您必须找到一个缺失的整数,这将不起作用,因为您可以在一开始就切断缺失的整数。

还有:

n + n/2 + n/4 + ... 1 <= 2n

不是n log n .

这是一个geometric sequencea = n, r = 1/2 ,可以用以下公式计算:

n (1-(1/2)^m)
-------------
1 - (1/2)

0 < (1/2)^m < 1对于任何正数 m (因为 0 < 1/2 < 1 ),我们可以说 (1-r^m) < 1因此我们可以说最大值是:

  n.1
-------
1 - 1/2

n
= ---
1/2

= 2n

关于algorithm - 编程珍珠 : Finding the missing integer in a file of 4 billion integers,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19398423/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com