编写一个程序，从10亿个数字中找出100个最大的数字
我最近参加了一次采访，在那里我被问及“编写一个程序，从10亿个数字中找出100个最大的数字。”
我只能给出一个蛮力解决方案，它将O（nlogn）时间复杂度的数组进行排序，并取最后的100个数字。
Arrays.sort(array);
面试官正在寻找更好的时间复杂性，我尝试了其他解决方案，但未能回答他。 有更好的时间复杂性解决方案吗？
您可以保留100个最大号码的优先队列，遍历十亿个号码，每当遇到一个大于队列中最小号码的数字（队列头部）时，删除队列头部并添加新号码到队列。
编辑：正如开发人员指出的，用堆实现的优先级队列，插入队列的复杂度为O(logN)
在最坏的情况下，你得到的billionlog2(100)是billionlog2(billion) billionlog2(100) ，比billionlog2(billion)
一般来说，如果您需要一组N个数中最大的K个数，则复杂度为O(NlogK)而不是O(NlogN) ，当K与N相比非常小时，这可能非常显着。
EDIT2：
该算法的预期时间非常有趣，因为在每次迭代中插入可能会或可能不会发生。 将第i个号码插入队列的概率是随机变量大于来自相同分布的至少iK随机变量（前k个号码自动添加到队列中）的概率。 我们可以使用订单统计（请参阅链接）来计算此概率。 例如，让我们假设数字是从{0, 1}中随机选择的，第（iK）个数字的期望值（我的数字之外）是(ik)/i ，并且随机变量的概率大于这个值是1-[(ik)/i] = k/i 。
因此，预期的插入次数是：
预期的运行时间可以表示为：
（ k时间产生具有前k元素的队列，然后nk比较，以及如上所述的期望插入次数，每个取平均log(k)/2时间）
请注意，当N比K NlogK ，这个表达式更接近n而不是NlogK 。 这个问题有点直观，就问题而言，即使在10000次迭代之后（与十亿次相比非常小），数字插入队列的机会非常小。
如果在采访中提到这一点，我认为面试官可能希望看到你的解决问题的过程，而不仅仅是你对算法的了解。
这个描述是相当一般的，所以也许你可以问他这些数字的范围或含义，以便明确问题。 这样做可能会给采访者留下深刻的印象。 例如，如果这些数字代表一个国家（例如中国）的人的年龄，那么这是一个更容易的问题。 在合理假设没有人活着超过200的情况下，您可以使用大小为200的int数组（可能为201）来计算一次迭代中具有相同年龄的人数。 这里的指数意味着年龄。 在此之后，找到100个最大号码是一块蛋糕。 顺便说一句，这个算法被称为计数排序 。
无论如何，让问题更具体和更清晰对你来说是有好处的。
你可以遍历数字，这需要O（n）
只要您找到大于当前最小值的值，请将新值添加到大小为100的循环队列中。
该循环队列的最小值是您的新比较值。 继续添加到该队列。 如果已满，请从队列中提取最小值。
链接地址: http://www.djcxy.com/p/70793.html上一篇: Write a program to find 100 largest numbers out of an array of 1 billion numbers