黑马程序员技术交流社区

标题: 求m个数据中的前10个最小数据 [打印本页]
作者: daoqin    时间: 2014-9-13 14:17
标题: 求m个数据中的前10个最小数据
假定现在有m个数据，无序的（m<=100万）
请你编程实现找出m个数据中前10最小的数据。时间限制：2000ms

作者: AlanHand    时间: 2014-9-13 14:17
  1. import java.util.Comparator;
  2. import java.util.Random;
  3. import java.util.Set;
  4. import java.util.TreeSet;

  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个数据，还好，没有超过两秒
作者: daoqin    时间: 2014-9-13 22:36
AlanHand 发表于 2014-9-13 17:21
其实用TreeSet在1000000中查找前十个数据时间并不长，长的是在treeSet中放入1000000个数据，还好，没有超 ...

我今天做了一下，感觉窍门在10个最小的数据，所以没必要把100万数据都放入set中，只要维护10个数据的set，每次加数据的时候判断是否比10个数据中最大的小，如果小就替换，最后输出这10个数据就可以了。
作者: AlanHand    时间: 2014-9-14 12:07
daoqin 发表于 2014-9-13 22:36
我今天做了一下，感觉窍门在10个最小的数据，所以没必要把100万数据都放入set中，只要维护10个数据的set ...

恩恩额恩，对头，我咋没有想到啦，但是会增加判断的消耗
作者: 毛毛毛玉    时间: 2014-9-19 18:38
本帖最后由 毛毛毛玉 于 2014-9-19 18:40 编辑

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




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2