最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?
最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?
当前回答
使用第n个元素得到第100个元素O(n) 迭代第二次,但只有一次,并输出大于此特定元素的所有元素。
请特别注意,第二步可能很容易并行计算!当你需要一百万个最大的元素时,它也会很有效。
其他回答
你可以在O(n)个时间内完成。只需遍历列表,并跟踪在任何给定点上看到的最大的100个数字,以及该组中的最小值。当你发现一个新的数字大于你的10个数字中的最小值,然后替换它并更新你的新的100的最小值(可能每次你都要花100的常数时间来确定,但这并不影响整体分析)。
我知道这可能会被埋没,但这是我对一个基MSD的变化的想法。
伪代码:
//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)左右。
快速解释一下这是为了做什么: 从本质上讲,这个系统试图基于数字中数字的索引和数字的值来使用2d数组中的每个数字。它使用这些值作为索引来跟踪数组中插入了多少数值。当达到100时,它会关闭所有“较低的分支”。
这个算法的时间大概是O(十亿*log(16)*7)+O(100)。我可能是错的。此外,这很可能需要调试,因为它有点复杂,我只是把它写在我的头上。
编辑:没有解释的反对票是没有帮助的。如果你认为这个答案不正确,请留下评论。我很确定,StackOverflow甚至告诉你这样做,当你向下投票。
管理一个单独的列表是额外的工作,每次你找到另一个替代物时,你都必须在整个列表中移动东西。把它排序,选前100名。
I would find out who had the time to put a billion numbers into an array and fire him. Must work for government. At least if you had a linked list you could insert a number into the middle without moving half a billion to make room. Even better a Btree allows for a binary search. Each comparison eliminates half of your total. A hash algorithm would allow you to populate the data structure like a checkerboard but not so good for sparse data. As it is your best bet is to have a solution array of 100 integers and keep track of the lowest number in your solution array so you can replace it when you come across a higher number in the original array. You would have to look at every element in the original array assuming it is not sorted to begin with.
取十亿个数字中的前一百个,然后排序。现在只需遍历十亿,如果源数大于100中最小的数,则按排序顺序插入。你得到的结果更接近于O(n)除以集合的大小。