假定现在有m个数据，无序的（m<=100万） 请你编程实现找出m个数据中前10最小的数据。时间限制：2000ms

1. import java.util.Comparator;
   
2. import java.util.Random;
   
3. import java.util.Set;
   
4. import java.util.TreeSet;
   
5. 
   
6. class Test
   
7. {
   
8.         public static void main(String[] args)
   
9.         {
   
10.                     //在treeSet中存放数据，自定义比较器
    
11.                 Set<Integer> set = new TreeSet<Integer>(new Comparator<Integer>() {
    
12.                                         @Override
    
13.                                         public int compare(Integer o1, Integer o2) {
    
14.                                                 return o1.intValue()>o2.intValue()?1:(o1.intValue()<o2.intValue()?-1:0);
    
15.                                         }
    
16.                        
    
17.                                 });  
    
18.                 //放入数据
    
19.                 for(int i=0;i<1000000;i++){
    
20.                         set.add(new Random().nextInt(1000000));
    
21.                 }
    
22.                
    
23.                 //查询：
    
24.                 System.out.println(System.currentTimeMillis()/1000);
    
25.                 int i = 0;
    
26.                 for(Integer s : set){
    
27.                         System.out.println(s);
    
28.                         i++;
    
29.                         if(i == 10){
    
30.                                 break;
    
31.                         }
    
32.                 }
    
33.                 System.out.println(System.currentTimeMillis()/1000);
    
34.                
    
35.         }
    
36. }

复制代码

其实用TreeSet在1000000中查找前十个数据时间并不长，长的是在treeSet中放入1000000个数据，还好，没有超过两秒

AlanHand 发表于 2014-9-13 17:21
其实用TreeSet在1000000中查找前十个数据时间并不长，长的是在treeSet中放入1000000个数据，还好，没有超 ...

我今天做了一下，感觉窍门在10个最小的数据，所以没必要把100万数据都放入set中，只要维护10个数据的set，每次加数据的时候判断是否比10个数据中最大的小，如果小就替换，最后输出这10个数据就可以了。

daoqin 发表于 2014-9-13 22:36
我今天做了一下，感觉窍门在10个最小的数据，所以没必要把100万数据都放入set中，只要维护10个数据的set ...

恩恩额恩，对头，我咋没有想到啦，但是会增加判断的消耗

如果真的只要十个的话，是不是存到LinkedList里面更好呢？红黑树存一百万个，也得有二十几层的高度了，还不如就用链表存10个数据，然后做比较。平均起来说不定还能快点呢。