java算法题 - ITeye问答

0 0

java算法题0

写一个算法：有10000000种不同的整型数。发现其最大的100要素。实施时应执行速度的优化。

2014年8月05日 15:14

郑云飞
1
0 0 11

采纳的答案

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;
	}
}

2014年8月05日 17:53

lasaka
30
0 0 5

添加评论

0 0

最快的做法时间复杂度就是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

2014年8月05日 18:55

red008
217
0 1 24