Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >如何在大量数据中找出第2大的数字

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

作者头像
一个架构师
发布于 2022-06-20 11:49:39
发布于 2022-06-20 11:49:39
93700
代码可运行
举报
运行总次数:0
代码可运行

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

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

例如:

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

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

在当前问题中,结果是41

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

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

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

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

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public TreeSet() {
    this(new TreeMap<E,Object>());
}

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

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

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

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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 删除

本文分享自 从码农的全世界路过 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Java集合-TreeMap源码解析-JDK1.8
TreeMap在jdk 1.8中使用用的是红黑树的结构来进行存储的,一个典型的红黑树就如下图所示:
Java学习录
2019/04/18
4080
Java集合-TreeMap源码解析-JDK1.8
集合系列 Map(十五):TreeMap
TreeMap 是 Map 集合的有序实现,其底层是基于红黑树的实现,能够早 log(n) 时间内完成 get、put 和 remove 操作。
陈树义
2019/08/29
8440
集合系列 Map(十五):TreeMap
多用多学之Java中的Set,List,Map
        很长时间以来一直代码中用的比较多的数据列表主要是List,而且都是ArrayList,感觉有这个玩意就够了。ArrayList是用于实现动态数组的包装工具类,这样写代码的时候就可以拉进拉出,迭代遍历,蛮方便的。         也不知道从什么时候开始慢慢的代码中就经常会出现HashMap和HashSet之类的工具类。应该说HashMap比较多一些,而且还是面试经典题,平时也会多看看。开始用的时候简单理解就是个键值对应表,使用键来找数据比较方便。随后深入了解后发现这玩意还有点小奥秘,特别是新版
用户1105954
2018/01/12
7600
死磕 java集合之TreeMap源码分析(二)- 内含红黑树分析全过程
插入元素,如果元素在树中存在,则替换value;如果元素不存在,则插入到对应的位置,再平衡树。
彤哥
2019/07/08
2440
死磕 java集合之TreeMap源码分析(二)- 内含红黑树分析全过程
TreeSet集合的add()方法的源码解析
用TreeSet存储Integer类型数据并遍历   20,18,23,22,17,24,19,18,24 1 package cn.itcast_05; 2 3 import java.util.TreeSet; 4 5 /* 6 * TreeSet:能够对元素按照某种规则进行排序。 7 * 排序有两种方式(具体那种方式取决于使用TreeSet的构造方法) 8 * A:自然排序 9 * B:比较器排序 10 *
黑泽君
2018/10/12
6380
【Java入门提高篇】Day30 Java容器类详解(十二)TreeMap详解
  今天来看看Map家族的另一名大将——TreeMap。前面已经介绍过Map家族的两名大将,分别是HashMap,LinkedHashMap。HashMap可以高效查找和存储元素,LinkedHashMap可以在高效查找的基础上对元素进行有序遍历,那么TreeMap又有什么特点呢?别急别急,看完这篇你就知道了。
弗兰克的猫
2018/09/03
2730
【Java入门提高篇】Day30 Java容器类详解(十二)TreeMap详解
Java集合深度解析之TreeMap
红黑树简介 TreeMap是基于红黑树实现的,这里只对红黑树做个简单的介绍,红黑树是一种特殊的二叉排序树,红黑树通过一些限制,使其不会出现二叉树排序树中极端的一边倒的情况,相对二叉排序树而言,这自然提
互扯程序
2018/03/26
8080
Java集合深度解析之TreeMap
TreeMap put 操作分析
1 public V put(K key, V value) { 2 //t 表示当前节点,记住这个很重要!先把TreeMap 的根节点root 的引用赋值给当前节点 3 TreeMap.Entry<K,V> t = root; 4 //如果当前节点为null ,即是空树,新增的KV 形成的节点就是根节点 5 if (t == null) { 6 //看似多此一举,实际上预检了Key 是否 可以比较 7
DougWang
2020/02/18
6750
JDK容器学习之TreeMap (一) : 底层数据结构
TreeMap 在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 LinkedHashMap,那么这个TreeMap到底是个怎样的容器,又适用于什么样的应用场景呢? 1. 数据结构分析 分析数据结构,最好的方式无疑是google+baidu+源码了 1. 继承体系 看到源码第一眼,就会发现与HashMap不同的是 TreeMap 实现的是 NavigableMap, 而不是直接实现 Map public class Tre
一灰灰blog
2018/02/06
2.1K0
源码研究——TreeMap
  继List之后,笔者又开始了Set与Map的源码探究,本次研究HashMap,HashSet,TreeMap,TreeSet。但是点进去后发现,HashSet与TreeSet点进去后其实就是HashMap与TreeMap。。。。。。先分析Map再分析Set
向着百万年薪努力的小赵
2022/12/02
3800
源码研究——TreeMap
【Java】基础篇- TreeMap
大家好久不见,我们今天来讲一下 Map 类的另一个重要实现 -- TreeMap。可能大家有的人会问道,我知道 Java 中有 HashMap ,我会用它就行了啊,我还学这个 TreeMap 做啥,其实 HashMap 有个很重要的问题,就是不能排序,或者说它的键值对不能按照特定的顺序排序。所以就引入了我们今天的 TreeMap。(记住 TreeMap 是按照键来进行排序的)而 TreeMap 的实现基础就是我们之前的上一篇文章提到的 排序二叉树,没有看的童鞋请移步:。
haoming1100
2019/06/19
7150
聊聊java中的哪些Map:(九)TreeMap源码分析
可以看到,TreeMap继承了AbstractMap,此外实现了NavigableMap、Cloneable和Serializable接口。而NavigableMap接口又继承了SortedMap。这与ConcurrentSkipListMap的情况类似,因而也是有序的。
冬天里的懒猫
2020/09/07
2310
聊聊java中的哪些Map:(九)TreeMap源码分析
java进阶|TreeMap源码分析
TreeMap是不是没用过?是的,我也没用过,但是我还是来进行分析它的方法了,因为我要了解一下这个键值对集合的方法有哪些?顺便思考一下它,因为我已经分析过TreeSet这种集合的源码了,如果TreeMap这种键值对集合不分析也不符合我的思考方式,其实对于键值对这种集合的使用场景还是蛮多的这里自己不会说具体的业务是如何做的,但是你可以自己思考思考,所以这里就说到这里,接下来的内容就是TreeMap源码的分析了。
码农王同学
2020/06/04
6660
Java集合Map接口详解——含源码分析
关于集合中的Collection我们已经讲完了,接下来我们一起来看集合中的另一个大类:Map
秋名山码神
2022/12/13
2310
Java集合Map接口详解——含源码分析
TreeMap源码解析
红黑树 就是一种平衡的二叉查找树,说他平衡的意思是他不会变成“瘸子”,左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外,还具体下列的特性:
103style
2022/12/19
3930
TreeMap源码解析
JDK1.8源码(十一)——java.util.TreeMap类
  在前面几篇博客分别介绍了这样几种集合,基于数组实现的ArrayList 类,基于链表实现的LinkedList 类,基于散列表实现的HashMap 类,本篇博客我们来介绍另一种数据类型,基于树实现的TreeSet类。
IT可乐
2019/05/25
4520
从源码解析TreeMap
Single
2018/01/04
6350
从源码解析TreeMap
TreeMap源码分析,看了都说好
TreeMap也是Map接口的实现类,它最大的特点是迭代有序,默认是按照key值升序迭代(当然也可以设置成降序)。在前面的文章中讲过LinkedHashMap也是迭代有序的,不过是按插入顺序或访问顺序,这与TreeMap需要区分开来。TreeMap内部用红黑树存储数据,而不是像HashMap、LinkedHashMap、WeakHashMap一样使用哈希表来存储。
李红
2019/09/10
4760
TreeMap源码分析,看了都说好
大数据必学Java基础(五十九):Map接口源码部分
实际上这个算法就是: h%length ,但是取模的话 效率太低,所以用位运算效率会很高。
Lansonli
2022/09/30
4502
大数据必学Java基础(五十九):Map接口源码部分
(43) 剖析TreeMap / 计算机程序的思维逻辑
40节介绍了HashMap,我们提到,HashMap有一个重要局限,键值对之间没有特定的顺序,我们还提到,Map接口有另一个重要的实现类TreeMap,在TreeMap中,键值对之间按键有序,TreeMap的实现基础是排序二叉树,上节我们介绍了排序二叉树的基本概念和算法,本节我们来详细讨论TreeMap。 除了Map接口,因为有序,TreeMap还实现了更多接口和方法,下面,我们先来看TreeMap的用法,然后探讨其内部实现。 基本用法 构造方法 TreeMap有两个基本构造方法: public Tre
swiftma
2018/01/31
9260
(43)  剖析TreeMap / 计算机程序的思维逻辑
相关推荐
Java集合-TreeMap源码解析-JDK1.8
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验