写一个程序从10亿个数组中找出100个最大的数
我只能给出一个强力解决方案，即以O（nlogn）时间复杂度对数组进行排序，并取最后100个数字。
Arrays.sort(array);
面试官在寻找一个更好的时间复杂性，我尝试了几个其他的解决方案，但都没能回答他。有更好的时间复杂性解决方案吗？
共有1个答案
您可以保留100个最大数字的优先队列，在遇到大于队列中最小数字（队列头部）的数字时，迭代10亿个数字，移除队列头部并将新数字添加到队列中。
Edit：正如Dev所指出的，使用堆实现的优先级队列，插入队列的复杂性是o(logN)
在最坏的情况下，您会得到BillionLog2(100)，这比billionLog2(billion)要好
编辑2：
这个算法的预期时间非常有趣，因为在每次迭代中可能会发生插入，也可能不会发生插入。第i个数被插入队列的概率是随机变量大于来自相同分布的至少i-k随机变量的概率（前k个数自动添加到队列中）。我们可以使用顺序统计（见链接）来计算这个概率。例如，假设这些数字是从{0,1}中随机一致地选择的，第（i-K）个数字（从i个数字中）的期望值是(i-K)/i，随机变量大于该值的几率是1-[(i-K)/i]=k/i。
因此，预期的插入数为：
而预期的运行时间可以表示为：
(k生成具有第一个k元素的队列的时间，然后是n-k比较，以及如上所述的预期插入数，每一个都需要平均log(k)/2时间）
请注意，当n与k相比非常大时，此表达式更接近n而不是nlogk。这有点直观，就像问题的情况一样，即使在10000次迭代之后（与10亿次相比，这是非常小的），一个数字被插入队列的机会也非常小。
-
本文向大家介绍从一个数组中找出前4个最大的数，用最优解。相关面试题，主要包含被问及从一个数组中找出前4个最大的数，用最优解。时的应答技巧和注意事项，需要的朋友参考一下
-
本文向大家介绍写一个函数找出给定数组中的最大差值相关面试题，主要包含被问及写一个函数找出给定数组中的最大差值时的应答技巧和注意事项，需要的朋友参考一下 function getMax(arr){ for(let i=arr[arr.length-1];i>0;i--){ for(let j=0;j<arr.length-i-1;j++){ if(arr[j]>arr[j+1]){ let temp
-
本文向大家介绍寻找一数组中前K个最大的数相关面试题，主要包含被问及寻找一数组中前K个最大的数时的应答技巧和注意事项，需要的朋友参考一下 考察点：数组
-
我有一个数组，我需要三个数中最大的一个数和各自的索引值。我有一个这样的数组： 如何找到最大的数字及其索引值？
-
问题内容： 最近有人要求我为一份工作编写3个测试程序。它们将仅使用核心Java API和我选择的任何测试框架来编写。应在适当的地方实施单元测试。 尽管我根本没有收到任何反馈，但我想他们不喜欢我的解决方案（否则我会收到他们的来信），所以我决定在这里展示我的程序，并询问这种实现是否可以认为是好的，并且，如果没有，那为什么呢？ 为避免混淆，我现在只问第一个。 实现一个函数，以在另一个更大的数组中查找一个
-
我无法完成这个问题。编写一个程序，搜索数组以找到第一个奇数。如果找到奇数，则找到奇数后的第一个偶数。返回第一个奇数和第一个偶数之间的距离。如果未找到奇数或奇数后没有偶数，则返回-1。我试过这个问题，但无法解决这是我的代码： 此代码的运行程序 请帮我完成这个代码，我给输出，这个代码给这个运行。我需要这个答案。我需要的正确输出。