最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?
最近我参加了一个面试,面试官要求我“编写一个程序,从一个包含10亿个数字的数组中找出100个最大的数字”。
我只能给出一个蛮力解决方案,即以O(nlogn)时间复杂度对数组进行排序,并取最后100个数字。
Arrays.sort(array);
面试官正在寻找一个更好的时间复杂度,我尝试了几个其他的解决方案,但都没有回答他。有没有更好的时间复杂度解决方案?
当前回答
我知道这可能会被埋没,但这是我对一个基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个最好使用包含100个元素的最小堆。
首先用遇到的前100个数字对最小堆进行质数。Min-heap将前100个数字中最小的存储在根(顶部)。
现在,当你继续计算其他数字时,只将它们与根数(100中最小的数)进行比较。
如果遇到的新数字大于最小堆的根,则将根替换为该数字,否则忽略它。
作为在最小堆中插入新数字的一部分,堆中最小的数字将移到顶部(根)。
一旦我们遍历了所有的数字,我们将得到最小堆中最大的100个数字。
可能的改进。
如果文件包含十亿的数字,读取它可能会很长…
为了提高工作效率,你可以:
将文件分成n个部分,创建n个线程,让n个线程在各自的部分中寻找最大的100个数字(使用优先级队列),最后得到所有线程输出的最大的100个数字。 使用像hadoop这样的解决方案,使用集群来完成这样的任务。在这里,您可以进一步分割文件,并更快地输出10亿(或10^12)个数字的文件。
这是谷歌或其他行业巨头提出的问题。也许下面的代码就是面试官想要的正确答案。 时间成本和空间成本取决于输入数组中的最大数量。对于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;
}
}
}
}
}
}
}
取十亿个数字中的前一百个,然后排序。现在只需遍历十亿,如果源数大于100中最小的数,则按排序顺序插入。你得到的结果更接近于O(n)除以集合的大小。
一个非常简单的解决方案是遍历该数组100次。也就是O(n)
每次取出最大的数字(并将其值更改为最小值,以便在下一个迭代中看不到它,或者跟踪以前答案的索引(通过跟踪索引,原始数组可以有多个相同的数字))。经过100次迭代,就得到了最大的100个数字。