最快的做法时间复杂度就是O(NlogK)
其中N是你的所有数据的大小,K是你想取最大的多少个。
具体说就是循环所有的数据N,然后往一个PriorityQueue里面放(如果你用的是Java的话),这个Queue每次插入会自动排序,所以你需要做的就是当PriorityQueue的大小大于100的时候,每次看你下面循环的元素是否比这个PriorityQueue的第一个元素大,如果是的话,就抛弃第一个元素,把你现在循环的元素放进去。
最后将PriorityQueue里面元素都打印出来就可以了。
你循环所有的数据的事件复杂度是O(N),那个PriorityQueue内部用的是堆排序,所以你可能会以为结果是O(NlogN),实际上,当N远远大于K的时候,结果是近似O(NlogK)的。
这个方法肯定是最快的了,想得到完美的数学证明的话,可以参考下面的文章:
http://stackoverflow.com/questions/19227698/write-a-program-to-find-100-largest-numbers-out-of-an-array-of-1-billion-numbers
import java.util.ArrayList; public class createDir { private static int num[] =new int [10000000]; private static ArrayList<Object> ans=null; public static void main(String[] arg){ for(int i = 0;i<10000000;i++){ num[i]= i+1; } boolean boo=true; int i = 0; while (boo) { int j = (int) (Math.random() * 10000000); int k = num[i]; num[i] = num[j]; num[j] = k; i++; if(i==100000){ boo =false; } } long start =System.currentTimeMillis(); ans = new ArrayList<Object>(); for(int j = 0;j<10000000;j++){ if(j<10){ ans = sort(ans,num[j]); }else{ if(num[j]>(Integer)ans.get(0)){ ans = getMaxValue(ans,num[j]); } } } long end =System.currentTimeMillis(); long total= (end-start); System.out.println(total + " ms"); System.out.println(ans); } private static ArrayList<Object> getMaxValue(ArrayList<Object> ans,int num){ for(int i=1;i<ans.size();i++){ if(num < (Integer) ans.get(i)){ ans.add(i,num); ans.remove(0); break; } if(i==ans.size()-1){ ans.add(num); ans.remove(0); break; } } return ans; } private static ArrayList<Object> sort(ArrayList<Object> ans,int num){ if(ans.size()>0){ int min = (Integer) ans.get(0); if(min>num){ ans.add(0, num); }else if(ans.size()==1){ ans.add(num); }else{ for(int i=1;i<ans.size();i++){ if(num < (Integer) ans.get(i)){ ans.add(i,num); break; } if(i==ans.size()-1){ ans.add(num); break; } } } }else{ ans.add(0, num); } return ans; } }
相关推荐
20位左右的大数相乘算法解析,用一个整型数组表示一个大数,数组的每个元素储存大数的一位数字,则实际的大数d表示为: d=a[k]*10的k-1次幂+a[k-1]*10的k-2次幂+......+a[2]*10+a[1] 其中a[0]保存该大数的位数. ...
用数组进行大数相乘,解决超整形的大数相乘
Java 语言实现的大数相加程序。一个简单算法的实现。此前,在学校学习时,用C++编码解决过这个问题,当时还没写出来。
大数相乘,超出整型最大数值时,不能直接进行乘法运算。将该数拆分,进行运算
常规的计算阶乘的方法是采用递归。但由于受计算机的限制,即时采用长整型也只能计算20以内的阶乘。自己写了一个计算大数乘法和阶乘的程序,感兴趣的可以看一看
集成了大整数的、加法、减法(仅限被减数大于减数)、乘法、乘以2、除以2、减去1、判断奇偶、判断是否为1等方法 乘法和加法经过多次测试和修改,基本上不存在什么问题,...可以用到大数算法中农夫算法、蛮力算法等等。
大数运算(超过整形,长整形数据类型)(0~10^100),加法运算
由于数字无法用一个整形变量存储,很自然的想到用字符串来表示一串数字。然后按照乘法的运算规则,用一个乘数的每一位乘以另一个乘数,然后将所有中间结果按正确位置相加得到最终结果。可以分析得出如果乘数为A和B,...
//将长整形数转换为对应的大数形式 void RsaDo(byteint source,byteint R,byteint key,byteint desti); //实现加解密 unsigned long Os2ip(unsigned char* pstr); CString Ip2os(CString str); public: void ...
VC 无符号大整数类计算方法,作者:缪元虎,四川绵阳供电局,重载的减法运算符,因为是无符号数,所以结果为大数减小数得到的差,乘2运算,即// a = a * 2^dwTimes; 相当于左移一位二进制,低位补0,除2运算;相当于...
由于普通的数据类型具有数据范围有限,计算机一次处理的数据长度也有限,因此需要一种算法实现超大数的计算。 此程序是将大数分段,一次处理,最后再将结果处理输出。 数据结构使用双向链表,其中有基本数据段和进位...
例如,定义一个函数, 用于求两个数中的大数,可写为: int max(a,b) int a,b; { if (a>b) return a; else return b; } 第一行说明max函数是一个整型函数,其返回的函数值是一个整数。形参为a,b。第二行说明a,b均...
cout乘法,除法和求余只能完成一定范围内数的运算"; } void add(char a[],char b[],int x,int y,int f,int d) { char c[102]; int i; int j; int jin=0; int s=0; int m,ma; int xx,yy; if(d==0) { xx=0;yy=0; } ...