DeTechn Blog

4G的long型整数中找到一个最大的,如何做?

要找到最大的肯定要遍历所有的数的,而且不能将数据全部读入内存,可能不足。算法的时间复杂度肯定是O(n)
感觉就是遍历,比较。。。。还能怎么改进呢????
可以改进的地方,就是读入内存的时候,一次多读些。。。。
需要注意的就是每次从磁盘上尽量多读一些数到内存区,然后处理完之后再读入一批。减少IO次数,自然能够提高效率。而对于类快速排序方法,稍微要麻烦一些: 分批读入,假设是M个数,然后从这M个数中选出n个最大的数缓存起来,直到所有的N个数都分批处理完之后,再将各批次缓存的n个数合并起来再进行一次类快 速排序得到最终的n个最大的数就可以了。在运行过程中,如果缓存数太多,可以不断地将多个缓存合并,保留这些缓存中最大的n个数即可。由于类快速排序的时 间复杂度是O(N),这样分批处理再合并的办法,依然有极大的可能会比堆和败者树更优。当然,在空间上会占用较多的内存。

此题还有个变种,就是寻找K个最大或者最小的数。有以下几种算法:
容量为K的最大堆/最小堆,假设K可以装入内存;
如果N个数可以装入内存,且都小于MAX,那么可以开辟一个MAX大的数组,类似计数排序。。。从数组尾部扫描K个最大的数,头部扫描K个最小的数。

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »