我最近参加了一次采访，当时我被要求“编写一个程序，从 10 亿个数字的数组中找出 100 个最大的数字”。
我只能给出一个蛮力解决方案，即以 O(nlogn) 时间复杂度对数组进行排序并取最后 100 个数字。
Arrays.sort(array);
面试官正在寻找更好的时间复杂度，我尝试了其他几个解决方案但未能回答他。有没有更好的时间复杂度解决方案？
问问题
68281 次
33 回答
332
您可以保留 100 个最大数字的优先级队列，遍历十亿个数字，每当遇到大于队列中最小数字（队列头）的数字时，删除队列头并添加新数字到队列。
编辑：
正如 Dev 所指出的，使用堆实现的优先级队列，插入队列的复杂性是O(log N)
在最坏的情况下，你会得到比billion*log2(100)billion*log2(billion)
一般来说，如果您需要一组 N 个数字中最大的 K 个数字，则复杂度是O(N log K)而不是O(N log N)，当 K 与 N 相比非常小时，这可能非常重要。
编辑2：
该算法的预期时间非常有趣，因为在每次迭代中可能会或可能不会发生插入。第 i 个数字插入队列的概率是随机变量至少大于i-K来自相同分布的随机变量的概率（前 k 个数字自动添加到队列中）。我们可以使用订单统计（见链接）来计算这个概率。例如，假设数字是从 中均匀随机选择的{0, 1}，第 (iK) 个数字（在 i 个数字中）的期望值为(i-k)/i，并且随机变量大于该值的机会为1-[(i-k)/i] = k/i。
因此，预期的插入次数为：
并且预期的运行时间可以表示为：
（k生成具有第一个k元素的队列的时间，然后n-k是比较，以及如上所述的预期插入次数，每个都需要平均log(k)/2时间）
请注意，当N与 相比非常大时K，此表达式更接近于n而不是N log K。这有点直观，就像问题的情况一样，即使经过 10,000 次迭代（与十亿相比非常小），将一个数字插入队列的机会也非常小。
于 2013-10-07T14:45:54.100 回答
142
如果在面试中问这个问题，我想面试官可能想看看你解决问题的过程，而不仅仅是你对算法的了解。
描述很笼统，所以也许你可以问他这些数字的范围或含义，以明确问题。这样做可能会给面试官留下深刻印象。例如，如果这些数字代表一个国家（例如中国）内人们的年龄，那么问题就容易多了。合理假设没有人活过 200 岁，您可以使用大小为 200（可能是 201）的 int 数组来计算一次迭代中具有相同年龄的人数。这里的索引是指年龄。在此之后，找到 100 个最大的数是小菜一碟。顺便说一下，这种算法称为计数排序。
无论如何，让问题更具体、更清晰对你在面试中是有好处的。
于 2013-10-08T18:04:09.667 回答
71
您可以遍历需要 O(n) 的数字
每当您发现大于当前最小值的值时，将新值添加到大小为 100 的循环队列中。
该循环队列的最小值是您的新比较值。继续添加到该队列。如果已满，则从队列中提取最小值。
于 2013-10-07T14:45:37.007 回答
35
我意识到这被标记为“算法”，但会抛出一些其他选项，因为它可能也应该被标记为“采访”。
10亿个数字的来源是什么？如果它是一个数据库，那么“按值 desc 限制 100 从表顺序中选择值”会很好地完成这项工作 - 可能存在方言差异。
这是一次性的，还是会重复的？如果重复，频率如何？如果是一次性的并且数据在文件中，则 'cat srcfile | 排序（根据需要选择）| head -100' 将让您快速完成您获得报酬的生产性工作，同时计算机处理这些琐碎的琐事。
如果重复，您会建议选择任何体面的方法来获取初始答案并存储/缓存结果，以便您能够持续报告前 100 名。
最后，还有这个考虑。您是否正在寻找入门级工作并与极客经理或未来的同事进行面试？如果是这样，那么您可以抛弃所有描述相关技术优缺点的方法。如果你正在寻找一份更具管理性的工作，请像经理一样对待它，关心解决方案的开发和维护成本，然后说“非常感谢”，如果面试官想专注于 CS 琐事，就离开. 他和你在那里不太可能有很大的晋升潜力。
祝下次面试好运。
于 2013-10-08T22:09:02.460 回答
17
My immediate reaction for this would be to use a heap, but there is way to use QuickSelect without keeping all of the input values on hand at any one time.
Create an array of size 200 and fill it up with the first 200 input values. Run QuickSelect and discard the low 100, leaving you with 100 free places. Read in the next 100 input values and run QuickSelect again. Continue until you have run though the entire input in batches of 100.
At the end you have the top 100 values. For N values you have run QuickSelect roughly N/100 times. Each Quickselect cost about 200 times some constant, so the total cost is 2N times some constant. This looks linear in the size of the input to me, regardless of the parameter size that I am hardwiring to be 100 in this explanation.
于 2013-10-07T18:50:36.543 回答
16
您可以使用快速选择算法在（按顺序）索引 [billion-101] 处查找数字，然后遍历数字并从该数字中找到更大的数字。
array={...the billion numbers...}
result[100];
pivot=QuickSelect(array,billion-101);//O(N)
for(i=0;i<billion;i++)//O(N)
if(array[i]>=pivot)
result.add(array[i]);
该算法时间为：2 XO(N) = O(N)（平均案例性能）
Thomas Jungblut建议的第二个选项是：
使用堆构建 MAX 堆将占用 O(N)，然后前 100 个最大数字将位于堆的顶部，您只需将它们从堆中取出 (100 XO(Log(N))。
该算法时间为：O(N) + 100 XO(Log(N)) = O(N)
于 2013-10-07T15:13:08.907 回答
10
尽管其他快速选择解决方案已被否决，但事实仍然是快速选择比使用大小为 100 的队列更快地找到解决方案。就比较而言，快速选择的预期运行时间为 2n + o(n)。一个非常简单的实现是
array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
if(array[i]>r)
add array[i] to result
这将平均进行 3n + o(n) 次比较。此外，使用快速选择将数组中最大的 100 个项目保留在最右边的 100 个位置这一事实可以提高效率。所以实际上运行时间可以提高到2n+o(n)。
存在的问题是这是预期的运行时间，而不是最坏的情况，但是通过使用合适的枢轴选择策略（例如随机选择 21 个元素，并选择这 21 个元素的中值作为枢轴），那么比较的次数可以是对于任意小的常数 c，以高概率保证最多为 (2+c)n。
实际上，通过使用优化的采样策略（例如随机采样 sqrt(n) 个元素，并选择第 99 个百分位数），对于任意小的 c，运行时间可以降低到 (1+c)n + o(n) （假设K，要选择的元素个数为o(n)）。
另一方面，使用大小为 100 的队列将需要 O(log(100)n) 次比较，并且 log base 2 of 100 大约等于 6.6。
如果我们从更抽象的意义上考虑这个问题，即从大小为 N 的数组中选择最大的 K 个元素，其中 K=o(N) 但 K 和 N 都趋于无穷大，那么 quickselect 版本的运行时间将是O(N) 并且队列版本将是 O(N log K)，所以从这个意义上说，快速选择也是渐近优越的。
在评论中，提到队列解决方案将在随机输入的预期时间 N + K log N 内运行。当然，除非问题明确说明，否则随机输入假设永远不会有效。可以使队列解决方案以随机顺序遍历数组，但这将导致 N 次调用随机数生成器以及置换整个输入数组或分配包含长度为 N 的新数组的额外成本随机指数。
如果问题不允许您在原始数组中移动元素，并且分配内存的成本很高，那么复制数组不是一种选择，那是另一回事。但严格来说，就运行时间而言，这是最好的解决方案。
于 2013-10-07T15:42:58.597 回答
5
取十亿的前 100 个数字并对其进行排序。现在只需遍历十亿，如果源数高于 100 中的最小值，则按排序顺序插入。你最终得到的是比集合大小更接近 O(n) 的东西。
于 2013-10-07T14:56:15.363 回答
4
两种选择：
（1）堆（priorityQueue）
维护一个大小为 100 的最小堆。遍历数组。一旦元素小于堆中的第一个元素，就替换它。
InSERT ELEMENT INTO HEAP: O（log100）
compare the first element: O(1)
There are n elements in the array, so the total would be O(nlog100), which is O(n)
(2) Map-reduce 模型。
这与 hadoop 中的字数统计示例非常相似。地图作业：统计每个元素出现的频率或次数。减少：获取前 K 个元素。
通常，我会给招聘人员两个答案。给他们任何他们喜欢的东西。当然，map reduce 编码会很费力，因为您必须知道每个确切的参数。练习它没有坏处。祝你好运。
于 2013-10-09T00:27:50.650 回答
4
一个非常简单的解决方案是遍历数组 100 次。这是O(n)。
每次拉出最大的数字（并将其值更改为最小值，以便在下一次迭代中看不到它，或跟踪先前答案的索引（通过跟踪原始数组可以具有的索引）相同数量的倍数））。在 100 次迭代后，您拥有 100 个最大的数字。
于 2013-10-09T15:41:54.717 回答
2
简单的解决方案是使用优先队列，将前 100 个数字添加到队列中并跟踪队列中最小的数字，然后遍历其他十亿个数字，每次我们找到一个大于最大数字的数字在优先队列中，我们删除最小的数字，添加新的数字，并再次跟踪队列中的最小数字。
如果数字是随机顺序的，这将很有效，因为当我们遍历十亿个随机数时，下一个数字很少会出现在迄今为止最大的 100 个中。但这些数字可能不是随机的。如果数组已经按升序排序，那么我们总是会在优先级队列中插入一个元素。
所以我们首先从数组中选择 100,000 个随机数。为了避免可能很慢的随机访问，我们添加了 250 个连续数字的 400 个随机组。通过这种随机选择，我们可以确定只有极少数剩余数字在前 100 位，因此执行时间将非常接近于将十亿个数字与某个最大值进行比较的简单循环的执行时间。
于 2016-04-04T18:42:33.237 回答
1
只需一行 C++ 代码，就可以用 N log(100) 复杂度（而不是 N log N）来回答这个问题。
std::vector<int> myvector = ...; // Define your 1 billion numbers.
// Assumed integer just for concreteness
std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());
最终答案将是一个向量，其中前 100 个元素保证是数组的 100 个最大数字，而其余元素是无序的
C++ STL（标准库）对于这类问题非常方便。
注意：我并不是说这是最佳解决方案，但它会挽救你的面试。
于 2013-10-27T15:12:26.597 回答
1
最简单的解决方案是扫描十亿个数字的大数组，并将迄今为止找到的 100 个最大值保存在一个小数组缓冲区中，无需任何排序，并记住该缓冲区的最小值。首先，我认为这种方法是由 fordprefect 提出的，但在评论中他说他假设 100 数字数据结构被实现为堆。每当找到一个更大的新数字时，缓冲区中的最小值就会被找到的新值覆盖，并再次在缓冲区中搜索当前最小值。如果十亿数数组中的数字大部分时间是随机分布的，则将大数组中的值与小数组的最小值进行比较并丢弃。仅对于非常小的数字部分，必须将值插入到小数组中。因此，可以忽略操纵包含小数字的数据结构的差异。对于少数元素，很难确定优先级队列的使用实际上是否比使用我的幼稚方法更快。
当扫描 10^9 元素数组时，我想估计小 100 元素数组缓冲区中的插入数量。程序扫描这个大数组的前 1000 个元素，并且必须在缓冲区中插入最多 1000 个元素。缓冲区包含扫描的 1000 个元素中的 100 个元素，即扫描元素的 0.1 个。所以我们假设大数组中的一个值大于缓冲区当前最小值的概率约为 0.1 这样一个元素必须插入到缓冲区中。现在程序从大数组中扫描接下来的 10^4 个元素。因为每次插入新元素时缓冲区的最小值都会增加。我们估计大于当前最小值的元素比例约为 0.1，因此要插入 0.1*10^4=1000 个元素。实际上，插入缓冲区的预期元素数量会更少。扫描完这 10^4 个元素后，缓冲区中的数字将是到目前为止扫描的元素的 0.01 左右。因此，在扫描接下来的 10^5 个数字时，我们假设不超过 0.01*10^5=1000 将插入缓冲区。继续这个论证，我们在扫描大数组的 1000+10^4+10^5+...+10^9 ~ 10^9 个元素后插入了大约 7000 个值。因此，当扫描具有 10^9 个随机大小元素的数组时，我们预计缓冲区中的插入不超过 10^4（=7000 向上舍入）。每次插入缓冲区后，必须找到新的最小值。如果缓冲区是一个简单的数组，我们需要 100 次比较才能找到新的最小值。如果缓冲区是另一个数据结构（如堆），我们至少需要 1 次比较才能找到最小值。要比较大数组的元素，我们需要 10^9 次比较。所以总而言之，当使用数组作为缓冲区时，我们需要大约 10^9+100*10^4=1.001 * 10^9 比较，而在使用另一种类型的数据结构（如堆）时，至少需要 1.000 * 10^9 比较. 因此，如果性能由比较次数决定，那么使用堆只会带来 0.1% 的增益。但是在 100 个元素的堆中插入一个元素和在 100 个元素的数组中替换一个元素并找到它的新最小值之间的执行时间有什么区别？使用另一种类型的数据结构（如堆）时进行 000 * 10^9 次比较。因此，如果性能由比较次数决定，那么使用堆只会带来 0.1% 的增益。但是在 100 个元素的堆中插入一个元素和在 100 个元素的数组中替换一个元素并找到它的新最小值之间的执行时间有什么区别？使用另一种类型的数据结构（如堆）时进行 000 * 10^9 次比较。因此，如果性能由比较次数决定，那么使用堆只会带来 0.1% 的增益。但是在 100 个元素的堆中插入一个元素和在 100 个元素的数组中替换一个元素并找到它的新最小值之间的执行时间有什么区别？
在理论层面：在堆中插入需要多少次比较。我知道它是 O(log(n)) 但常数因子有多大？我
在机器级别：缓存和分支预测对堆插入和数组中的线性搜索的执行时间有什么影响。
在实现层面：库或编译器提供的堆数据结构中隐藏了哪些额外成本？
我认为这些是在尝试估计 100 个元素堆或 100 个元素数组的性能之间的真正差异之前必须回答的一些问题。因此，进行实验并测量实际性能是有意义的。
于 2013-10-08T14:35:44.050 回答
1
Although in this question we should search for top 100 numbers, I will
generalize things and write x. Still, I will treat x as constant value.
算法 n 中最大的 x 个元素：
我将调用返回值LIST。它是一组 x 元素（在我看来应该是链表）
- 第一个 x 元素从池中“来时”取出并在 LIST 中排序（这是在恒定时间内完成的，因为 x 被视为常数 - O( x log(x) ) 时间）
- 对于接下来出现的每个元素，我们检查它是否大于 LIST 中的最小元素，如果是，我们会弹出最小的元素并将当前元素插入 LIST。因为这是有序列表，所以每个元素都应该在对数时间（二进制搜索）中找到它的位置，并且因为它是有序列表，所以插入不是问题。每一步也是在恒定时间（ O(log(x) ) 时间）内完成的。
那么，最坏的情况是什么？
x log(x) + (nx)(log(x)+1) = nlog(x) + n - x
所以这是最坏情况的 O(n) 时间。+1 是检查数字是否大于 LIST 中的最小数字。平均情况的预期时间将取决于这 n 个元素的数学分布。
可能的改进
对于最坏的情况，可以稍微改进该算法，但恕我直言（我无法证明这一说法）会降低平均行为。渐近行为将是相同的。
该算法的改进将是我们不会检查元素是否大于最小。对于每个元素，我们将尝试插入它，如果它小于最小元素，我们将忽略它。尽管如果我们只考虑最坏的情况，这听起来很荒谬
x log(x) + (nx)log(x) = nlog(x)
操作。
对于这个用例，我看不到任何进一步的改进。然而你必须问自己——如果我必须这样做超过 log(n) 次并且对于不同的 x-es 怎么办？显然，我们会在 O(n log(n)) 中对该数组进行排序，并在需要时获取我们的 x 元素。
于 2013-10-25T12:49:16.210 回答
1
受@ron Teller 回答的启发，这里有一个准系统 C 程序可以做你想做的事。
#include <stdlib.h>
#include <stdio.h>
#define TOTAL_NUMBERS 1000000000
#define N_TOP_NUMBERS 100
int
compare_function(const void *first, const void *second)
{
int a = *((int *) first);
int b = *((int *) second);
if (a > b){
return 1;
}
if (a < b){
return -1;
}
return 0;
}
int
main(int argc, char ** argv)
{
if(argc != 2){
printf("please supply a path to a binary file containing 1000000000"
"integers of this machine's wordlength and endianness\n");
exit(1);
}
FILE * f = fopen(argv[1], "r");
if(!f){
exit(1);
}
int top100[N_TOP_NUMBERS] = {0};
int sorts = 0;
for (int i = 0; i < TOTAL_NUMBERS; i++){
int number;
int ok;
ok = fread(&number, sizeof(int), 1, f);
if(!ok){
printf("not enough numbers!\n");
break;
}
if(number > top100[0]){
sorts++;
top100[0] = number;
qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function);
}
}
printf("%d sorts made\n"
"the top 100 integers in %s are:\n",
sorts, argv[1] );
for (int i = 0; i < N_TOP_NUMBERS; i++){
printf("%d\n", top100[i]);
}
fclose(f);
exit(0);
}
在我的机器上（带有快速 SSD 的核心 i3）需要 25 秒，1724 次排序。dd if=/dev/urandom/ count=1000000000 bs=1我为此运行生成了一个二进制文件。
显然，一次仅从磁盘读取 4 个字节存在性能问题，但这是为了举例。从好的方面来说，只需要很少的内存。
于 2013-10-09T00:31:36.007 回答
1
最好使用100 个元素的最小堆来从十亿个数字中找出前 100 个。
首先用遇到的前 100 个数字素数最小堆。min-heap 将在根（顶部）存储前 100 个数字中最小的一个。
现在，当您继续其余数字时，只需将它们与根（100 中的最小者）进行比较。
如果遇到的新数字大于 min-heap 的根，则用该数字替换根，否则忽略它。
作为在 min-heap 中插入新数字的一部分，堆中的最小数字将到达顶部（根）。
一旦我们遍历了所有数字，我们将在最小堆中拥有最大的 100 个数字。
于 2017-11-24T10:55:00.403 回答
0
我会找出谁有时间将十亿个数字放入数组中并解雇他。必须为政府工作。至少如果你有一个链表，你可以在中间插入一个数字，而不需要移动十亿来腾出空间。更好的 Btree 允许进行二分搜索。每次比较都会消除一半的总数。哈希算法将允许您像棋盘一样填充数据结构，但对于稀疏数据不太好。最好的办法是拥有一个由 100 个整数组成的解决方案数组，并跟踪解决方案数组中的最小数字，以便在原始数组中遇到更高数字时替换它。您必须查看原始数组中的每个元素，假设它一开始没有排序。
于 2013-10-09T15:11:46.190 回答
0
我看到了很多 O(N) 的讨论，所以我提出了一些不同的想法，只是为了思考练习。
是否有任何关于这些数字性质的已知信息？如果它本质上是随机的，那就不要再去看看其他答案了。你不会得到比他们更好的结果。
然而！查看是否有任何列表填充机制以特定顺序填充该列表。它们是否处于明确定义的模式中，您可以肯定地知道最大数量的数字将出现在列表的某个区域或某个区间内？它可能有一个模式。如果是这样，例如，如果它们保证处于某种正态分布中，中间有特征驼峰，在定义的子集之间总是有重复的上升趋势，在数据中间的某个时间 T 有一个长时间的尖峰设置为可能发生内幕交易或设备故障，或者在灾难后的力量分析中每隔 N 个数字设置一个“峰值”，您可以显着减少必须检查的记录数量。
无论如何，还是有一些值得深思的。也许这会帮助你给未来的面试官一个深思熟虑的答案。我知道如果有人问我这样的问题来回答这样的问题，我会印象深刻 - 它会告诉我他们正在考虑优化。只要认识到可能并不总是有可能进行优化。
于 2013-10-08T20:33:55.337 回答
0
如果有人感兴趣，我已经用 Python 编写了一个简单的解决方案。它使用bisect模块和一个保持排序的临时返回列表。这类似于优先级队列实现。
import bisect
def kLargest(A, k):
'''returns list of k largest integers in A'''
ret = []
for i, a in enumerate(A):
# For first k elements, simply construct sorted temp list
# It is treated similarly to a priority queue
if i < k:
bisect.insort(ret, a) # properly inserts a into sorted list ret
# Iterate over rest of array
# Replace and update return array when more optimal element is found
else:
if a > ret[0]:
del ret[0] # pop min element off queue
bisect.insort(ret, a) # properly inserts a into sorted list ret
return ret
使用 100,000,000 个元素和最坏情况输入（排序列表）：
>>> from so import kLargest
>>> kLargest(range(100000000), 100)
[99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907,
99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915,
99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923,
99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931,
99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939,
99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947,
99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955,
99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963,
99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971,
99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979,
99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987,
99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995,
99999996, 99999997, 99999998, 99999999]
计算 100,000,000 个元素大约需要 40 秒，所以我害怕为 10 亿个元素计算它。不过公平地说，我给它提供了最坏情况的输入（讽刺的是，一个已经排序的数组）。
于 2013-10-07T20:28:14.090 回答
0
Time ~ O(100 * N)
Space ~ O(100 + N)
创建一个包含 100 个空槽的空列表
对于输入列表中的每个数字：
如果数字小于第一个，跳过
否则用这个号码代替
然后，通过相邻的swap将数字推入；直到它小于下一个
返回列表
注意：如果是log(input-list.size) + c < 100，那么最佳方法是对输入列表进行排序，然后拆分前 100 个项目。
于 2013-10-09T06:19:07.300 回答
0
另一个 O(n) 算法 -
该算法通过消除找到最大的 100
考虑二进制表示中的所有百万数字。从最重要的位开始。查找 MSB 是否为 1 可以通过布尔运算乘以适当的数字来完成。如果这百万个中有超过 100 个 1，则用零消除其他数字。现在剩下的数字继续下一个最高有效位。计算淘汰后剩余数字的数量，只要该数字大于 100 就继续。
主要的布尔运算可以在 GPU 上并行完成
于 2013-10-09T12:40:14.690 回答
0
你可以O(n)及时完成。只需遍历列表并跟踪您在任何给定点看到的 100 个最大数字以及该组中的最小值。当你找到一个比你的十个中最小的更大的新数字时，然后替换它并更新你的新最小值 100（每次执行时可能需要一个恒定的时间 100 来确定这一点，但这不会影响整体分析）。
于 2013-10-09T15:37:35.107 回答
0
- 使用第 n 个元素获取第 100 个元素 O(n)
- 第二次但仅迭代一次并输出大于该特定元素的每个元素。
请注意，特别是。第二步可能很容易并行计算！当你需要一百万个最大的元素时，它也会很有效。
于 2013-10-11T08:01:42.217 回答
0
管理单独的列表是额外的工作，每次找到另一个替代品时，您都必须在整个列表中移动内容。只需 qsort 并获得前 100 名。
于 2013-10-09T16:32:56.353 回答
0
复杂度为 O(N)
首先创建一个 100 个整数的数组，将该数组的第一个元素初始化为 N 个值的第一个元素，用另一个变量跟踪当前元素的索引，称为 CurrentBig
迭代 N 个值
if N[i] > M[CurrentBig] {
M[CurrentBig]=N[i]; ( overwrite the current value with the newly found larger number)
CurrentBig++; ( go to the next position in the M array)
CurrentBig %= 100; ( modulo arithmetic saves you from using lists/hashes etc.)
M[CurrentBig]=N[i]; ( pick up the current value again to use it for the next Iteration of the N array)
}
完成后，将 CurrentBig 中的 M 数组打印 100 次模 100 :-) 对于学生：确保代码的最后一行在代码退出之前不会胜过有效数据
于 2013-10-09T08:42:24.320 回答
0
这是来自谷歌或其他一些行业巨头的问题。也许下面的代码是面试官期望的正确答案。时间成本和空间成本取决于输入数组中的最大数量。对于 32 位 int 数组输入，最大空间成本为 4 * 125M 字节，时间成本为 5 * 十亿。
public class TopNumber {
public static void main(String[] args) {
final int input[] = {2389,8922,3382,6982,5231,8934
,4322,7922,6892,5224,4829,3829
,6892,6872,4682,6723,8923,3492};
//One int(4 bytes) hold 32 = 2^5 value,
//About 4 * 125M Bytes
//int sort[] = new int[1 << (32 - 5)];
//Allocate small array for local test
int sort[] = new int[1000];
//Set all bit to 0
for(int index = 0; index < sort.length; index++){
sort[index] = 0;
}
for(int number : input){
sort[number >>> 5] |= (1 << (number % 32));
}
int topNum = 0;
outer:
for(int index = sort.length - 1; index >= 0; index--){
if(0 != sort[index]){
for(int bit = 31; bit >= 0; bit--){
if(0 != (sort[index] & (1 << bit))){
System.out.println((index << 5) + bit);
topNum++;
if(topNum >= 3){
break outer;
}
}
}
}
}
}
}
于 2013-10-13T09:35:03.620 回答
0
我做了我自己的代码，不确定它是否是“面试官”
private static final int MAX=100;
PriorityQueue<Integer> queue = new PriorityQueue<>(MAX);
queue.add(array[0]);
for (int i=1;i<array.length;i++)
{
if(queue.peek()<array[i])
{
if(queue.size() >=MAX)
{
queue.poll();
}
queue.add(array[i]);
}
}
于 2015-05-11T21:04:20.407 回答
0
首先取 1000 个元素并将它们添加到最大堆中。现在取出前最多 100 个元素并将其存储在某个地方。现在从文件中选择接下来的 900 个元素并将它们与最后 100 个最高元素一起添加到堆中。
不断重复这个从堆中取出 100 个元素并从文件中添加 900 个元素的过程。
100 个元素的最终选择将为我们提供 10 亿个数字中的最多 100 个元素。
于 2019-02-14T03:19:23.487 回答
0
可能的改进。
如果文件包含 10 亿个数字，读取它可能会很长......
为了改进这项工作，您可以：
- 将文件拆分为 n 个部分，创建 n 个线程，让 n 个线程各自查找文件中其所在部分的 100 个最大数（使用优先级队列），最后得到所有线程输出的最大 100 个数。
- 使用集群来完成这样的任务，使用类似 hadoop 的解决方案。在这里，您可以进一步拆分文件，并更快地输出 10 亿（或 10^12）个数字文件。
于 2016-08-02T01:27:32.327 回答
-1
问题：找到 n 个项目的 m 个最大元素，其中 n >>> m
每个人都应该明白的最简单的解决方案是简单地执行 m 次冒泡排序算法。
然后打印出数组的最后 n 个元素。
这不需要外部数据结构，并使用每个人都知道的算法。
运行时间估计为 O(m*n)。到目前为止最好的答案是 O(n log(m))，所以这个解决方案对于小 m 来说并没有显着增加。
我并不是说这无法改进，但这是迄今为止最简单的解决方案。
于 2013-10-08T14:47:44.973 回答
-1
此代码用于在Unsorted array中查找N个最大数。
#include <iostream>
using namespace std;
#define Array_Size 5 // No Of Largest Numbers To Find
#define BILLION 10000000000
void findLargest(int max[], int array[]);
int checkDup(int temp, int max[]);
int main() {
int array[BILLION] // contains data
int i=0, temp;
int max[Array_Size];
findLargest(max,array);
cout<< "The "<< Array_Size<< " largest numbers in the array are: \n";
for(i=0; i< Array_Size; i++)
cout<< max[i] << endl;
return 0;
}
void findLargest(int max[], int array[])
{
int i,temp,res;
for(int k=0; k< Array_Size; k++)
{
i=0;
while(i < BILLION)
{
for(int j=0; j< Array_Size ; j++)
{
temp = array[i];
res= checkDup(temp,max);
if(res == 0 && max[j] < temp)
max[j] = temp;
}
i++;
}
}
}
int checkDup(int temp, int max[])
{
for(int i=0; i<N_O_L_N_T_F; i++)
{
if(max[i] == temp)
return -1;
}
return 0;
}
这可能不是有效的，但可以完成工作。
希望这可以帮助
于 2013-10-09T15:36:21.617 回答
-1
我知道这可能会被埋没，但这是我对radix MSD.
pseudo-code:
//billion is the array of 1 billion numbers
int[] billion = getMyBillionNumbers();
//this assumes these are 32-bit integers and we are using hex digits
int[][] mynums = int[8][16];
for number in billion
putInTop100Array(number)
function putInTop100Array(number){
//basically if we got past all the digits successfully
if(number == null)
return true;
msdIdx = getMsdIdx(number);
msd = getMsd(number);
//check if the idx above where we are is already full
if(mynums[msdIdx][msd+1] > 99) {
return false;
} else if(putInTop100Array(removeMSD(number)){
mynums[msdIdx][msd]++;
//we've found 100 digits here, no need to keep looking below where we are
if(mynums[msdIdx][msd] > 99){
for(int i = 0; i < mds; i++){
//making it 101 just so we can tell the difference
//between numbers where we actually found 101, and
//where we just set it
mynums[msdIdx][i] = 101;
}
}
return true;
}
return false;
}
该函数getMsdIdx(int num)将返回最高有效数字（非零）的索引。该函数getMsd(int num)将返回最高有效位。该功能removeMSD(int num)将从数字中删除最高有效数字并返回该数字（如果在删除最高有效数字后没有任何内容，则返回 null）。
完成此操作后，剩下的就是遍历mynums以获取前 100 位数字。这将是这样的：
int[] nums = int[100];
int idx = 0;
for(int i = 7; i >= 0; i--){
int timesAdded = 0;
for(int j = 16; j >=0 && timesAdded < 100; j--){
for(int k = mynums[i][j]; k > 0; k--){
nums[idx] += j;
timesAdded++;
idx++;
}
}
}
我应该注意，虽然上面看起来它具有很高的时间复杂度，但它实际上只会在O(7*100).
快速解释这是试图做什么：本质上，这个系统试图根据数字中数字的索引和数字的值来使用二维数组中的每个数字。它使用这些作为索引来跟踪数组中插入了多少个该值。当达到 100 时，它会关闭所有“较低的分支”。
这个算法的时间是这样的O(billion*log(16)*7)+O(100)。我可能是错的。此外，这很可能需要调试，因为它有点复杂，我只是把它写在我的脑海中。
编辑：没有解释的否决票没有帮助。如果您认为此答案不正确，请留下评论原因。很确定 StackOverflow 甚至会在您投反对票时告诉您这样做。
于 2013-10-08T23:53:16.617 回答
-3
最近我正在调整一个理论，即世界上所有的问题都可以用 O(1) 来解决。甚至这个。从问题中不清楚数字的范围是多少。如果数字的范围是从 1 到 10，那么前 100 个最大的数字可能是 10 个一组。当最大数字比较小时，从 10 亿个数字中选出最大数字的机会到10亿是很大的。所以我会在那次采访中给出这个答案。
于 2013-10-15T19:35:39.937 回答