如何在大量数据中找出第2大的数字

一个架构师

发布于 2022-06-20 19:49:39

8870

发布于 2022-06-20 19:49:39

文章被收录于专栏：从码农的全世界路过

如何在大量数据中找出第2大的数字?

这个问题与TopN很类似,但也有不同

例如:

数组nums={42, 41, 31, 7, 17, 2, 42}

在top2时,结果是{42,42}

在当前问题中,结果是41

不同之处就在于对相同数字的判断.

了解topN解决方式的一定知道这种情况二叉查找树是一个最优选择;

针对相同数字的问题,最合适的去重数据结构就Set.

最终符合这两种条件的数据结构就是TreeSet.

通过观察源码可以发现,TreeSet的本质居然是TreeMap

public TreeSet() {
    this(new TreeMap<E,Object>());
}

观察继承关系可以发现TreeMap是继承SortedMap的,这就说明它是有序的.

也可以按自定义比较规则排序.

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

通过观察put方法,可以通过比较器,自定义规则,放新插入的值放入合适的位置

fixAfterInsertion(e)方法会对树(实际是红黑树)进行旋转维护.

public V put(K key, V value) {
    Entry<K,V> t = root;
      ...
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
   ...
Entry<K,V> e = new Entry<>(key, value, parent);
    fixAfterInsertion(e);
   ...
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-04-29，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构