并非排序


题:
在若干的元素中求出最大的前5个元素。
比如:23,15,26,38,33,22,19,17,21,35,47,2,18, ...
当然,你可以对所有的元素排序,然后找出最大的5个元素,但这样做实际上是做了不必要的多余的工作。如果元素较多,实现完全排序必然很浪费资源,而我们只要前5个元素,其它排好了序,也没什么用处!
请仔细设计一下解法,能够避开全排序。

源码SmartSorting.java


import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;
import java.util.Iterator;

class K4 implements Comparator<Object> {
    public int compare(Object a, Object b) {
        if (a instanceof Integer == false || 
                b instanceof Integer == false) {
            return 0;
        }
        int x1 = (Integer) a;
        int x2 = (Integer) b;
        return x2-x1;
    }
}

public class SmartSorting {
    public static void main(String args[]) {
        int[] lst = {23, 15, 26, 38, 33, 22, 19, 17, 21, 35, 47, 2, 18};
        Set<Integer> s = new TreeSet<Integer>(new K4());
        for (int i=0; i<lst.length; i++) {
            s.add(lst[i]);
        }
        Iterator<Integer> ite = s.iterator();
        for (int i=0; i<5; i++) {
            if (ite.hasNext()) {
                System.out.println(ite.next());
            }
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注