因为它们产生

Question

我正在写一个程序比需要找到一组号码中的第N个最大的值算出一组号码在第N个最大值。这些数字是由程序生成的，但我没有足够的内存来存储N个数字。是否有比N更好的上限，可以存储？这组数字（和N）的大小的上限约为100,000,000。

注：数字是小数和列表可以包括重复。

[编辑]：我的内存限制为16 MB。

Answer 1

这是一种多通道算法（因此，您必须能够多次生成相同的列表，或将列表存储到辅助存储中）。

第一遍：

• 找到的最高值和最低值。这是你的初始范围。第一后

通行证：

1. 除以的范围内成10个等间隔箱。我们不需要在垃圾箱中存储任何数字。我们只是要计算垃圾箱的会员资格。所以我们只需要一个整数数组（或者bigint - 任何可以准确地保存我们的计数的数值）。注意10是任意数量的分箱。您的样本量和分布将决定最佳选择。
2. 通过旋转数据中的每个数字，增加您看到的数量的二者之一的计数。
3. 找出哪个垃圾箱有答案，并将该垃圾箱上方的数字添加到获奖垃圾箱上方的数字计数。
4. 获奖箱的顶部和底部范围是您的新范围。
5. 再次循环这些步骤，直到您有足够的内存来保存当前文件夹中的数字。

最后一关：

• 你应该知道有多少数字是当前二进制上面现在。
• 您有足够的存储空间来抓取当前垃圾箱范围内的所有数字，因此您可以旋转并获取实际数字。只需对它们进行排序并获取正确的编号。

例如：如果你看到的范围是0.0到1000.0，你的垃圾箱的范围将是：

(- 0.0 - 100.0] 
(100.0 - 200.0] 
(200.0 - 300.0] 
... 
(900.0 - 1000.0) 

如果你通过你的电话号码为（100.0计数发现 - 2000.0]斌，你的下集箱的将是：

(100.0 - 110.0] 
(110.0 - 120.0] 
etc. 

---

另一种多通道的想法：

只需进行二分查找。选择范围的中点作为第一次猜测。你的通行证只需要做一个高于/低于计数来确定下一个估计值（可以通过计数来加权，或者为简化代码而简单地进行平均）。

Answer 2

如果我理解好，您的程序上限的内存使用情况是O（N）（可能N + 1）。您可以维护生成的值的列表，该列表比当前X（迄今为止的第N个最大值）大，按照最低的顺序排列。只要生成一个新的更大的值，就可以将当前的X替换为列表的第一个元素，并将刚刚生成的值插入列表中的相应位置。

Answer 3

排序-n | uniq的-c和第N应该是第N行

Answer 4

这类似于另一个问题 - C Program to search n-th smallest element in array without sorting? - 在这里你可以得到一些答案。
该逻辑将同样适用于第N大/最小的搜索。
注意：我不是说这是重复的。

---

由于您有很多（接近10亿？）数字，这里是空间优化的另一种方法。
假设您的数字适合32位值，那么大约10亿将需要一段时间接近32GB的空间。现在，如果您可以承受大约128MB的工作内存，我们可以一次完成。

1. 想象存储为32位字的阵列1十亿位向量
   • 让它被初始化为全零
   • 开始通过你的号码运行并保持设定正确的位位置数的值
   • 当你与一个一遍完成，开始从该位向量开始计数第N集位
   • 该位的位置让你的第N个数量最多
   价值
   • 实际上，你已经整理过程中的所有的数字（但是，重复的次数不跟踪）

Answer 5

您能够再生同一组从开始的数字？如果是的话，可以在输出上多次传递：首先找到最大值，重新启动发生器，找到最小的数字，重新启动发生器，并重复此操作直到得到结果。

这将是一个真正的表现杀手，因为你有很多数字，并且需要很多通行证 - 但是在记忆方面，你只需要存储2个元素（当前最大值和一个“限制“，你在上一次传球中找到的号码）和一个传球计数器。

您可以通过使用优先级队列找到M个最大元素加快它（选择数μm，你能够装入内存），让您减少需要N/M的遍数。

如果您需要查找15个数字列表中的第10个最大元素，则可以通过其他方式节省时间。由于它是第10大元素，这意味着有15-10 = 5个元素比这个元素小 - 所以你可以找第6个最小的元素来代替。