【数据结构】mapset详解

在这里插入图片描述

🍁1. Set系列集合

Set接口是一种不包含重复元素的集合。它继承自Collection接口,所以可以使用Collection所拥有的方法,Set接口的实现类主要有HashSetLinkedHashSetTreeSet等,它们各自以不同的方式存储元素,但都遵循Set接口的规定。

  • 当你需要确保集合中的元素唯一时。
  • 当你不需要保持元素的插入顺序时(除非使用LinkedHashSet)。
  • 当你需要元素自然排序或根据自定义排序规则排序时(使用TreeSet)。

🍁1.1 HashSet 

当用HashSet实例化对象时,由于底层结构是哈希表,所以元素是无序的,而TreeSet底层是红黑树,是有序的

 由于Set系列集合里面不能有重复的元素,在之前我们也了解到,add方法的返回值是boolean类型的,当遇到重复元素,第二次添加就会添加失败

并且Set集合没有索引的概念,不能通过下标的方式进行遍历打印

 和之前一样,没有索引的集合可以通过迭代器,增强for,lambda表达式进行遍历

        Iterator<String> it = s1.iterator();while (it.hasNext()){System.out.print(it.next() + " ");}System.out.println();for(String s : s1){System.out.print(s + " ");}System.out.println();s1.forEach(new Consumer<String>() {@Overridepublic void accept(String s) {System.out.print(s + " ");}});

 🍁1.2 LinkedHashSet

 LinkedHashSet底层也是哈希表,但是存取元素的顺序是一致的,因为使用了双向链表记录添加顺序

🍁1.3 TreeSet

TreeSet是基于红黑树实现的,TreeSet中的元素处于排序状态,因此查找、添加、删除和遍历等操作都能以对数时间复杂度进行。但是,TreeSet中添加的元素必须实现Comparable接口,或者在创建TreeSet时提供一个Comparator对象,以确保元素可以被正确地排序。

 排序规则:Integer,Double等数值类型默认按照从小到大的顺序排序,对于字符,字符串类型,按照ASCII码表中的数字进行升排序 

 接下来演示一下,创建自定义类型的TreeSet

例如:给出一个Student类,要求按照学生的年龄排序

首先创建好Student类之后,需要实现Comparable接口,然后重写compareTo和toString方法

public class Student implements Comparable<Student>{public String name;public int age;public Student(String name, int age) {this.name = name;this.age = age;}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic int compareTo(Student o) {return this.age - o.age;//this.age表示要添加的元素}
}

 this.age表示要添加的元素,所以如果返回值是负数,表示要添加的元素是小的,存左边,如果是0,表示元素已经存在,直接舍弃

public class Text2 {public static void main(String[] args) {Student s1 = new Student("zhang",18);Student s2 = new Student("wang",20);Student s3 = new Student("li",19);TreeSet<Student> treeSet = new TreeSet<>();treeSet.add(s1);treeSet.add(s2);treeSet.add(s3);System.out.println(treeSet);}
}

 最终,虽然插入时没有按顺序,由于TreeSet底层是红黑树,所以最终也实现了排序的效果

 比较器排序

问题:根据字符串长度比较,长度相同再按字典序比较

        //o1:当前要添加的元素//o2:红黑树中已经存在的元素TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return (o1.length() - o2.length()) == 0 ? o1.compareTo(o2) : o1.length() - o2.length();}});ts.add("bbcd");ts.add("abcde");ts.add("abcd");System.out.println(ts);

也就是在创建对象的时候传入比较器进行比较

🍁2. 单列集合的使用场景分析

介绍完Set系列集合之后,我们的单列集合就都学习完了,接下来分析一下这写集合的使用场景

如果集合中元素可重复:使用ArrayList(基于数组)

如果集合中元素可重复并且用到增删操作多余查询:使用LinkedList

如果需要对集合去重:使用HashSet

如果需要在去重的前提下还要保证存取顺序:使用LinkedHashSet

如果需要对集合中的元素进行排序:使用TreeSet

🍁3. Map系列集合

Map系列的集合称为双列集合

1. 双列集合一次存储一对数据,分别为键和值

2. 键不能重复,值可以重复

3. 键和值是一一对应的,每一个键都对应一个值

4. 键+值整体称为键值对,也叫Entry对象

 和Set集合类似,Map是顶层接口,底下有这些实现类

以下就是Map集合常用的API

🍁3.1 HashMap

HashMap的底层也是哈希表,和之前的HashSet不同,HashMap中,当插入的key相同时,第二次插入会覆盖原来的value值,同时,如果存储的是自定义类型的对象还需要重写HashCode和equals方法

其他方法就不演示了,下面来介绍一下map的遍历

Map的遍历

键找值:调用keySet方法,获取所有的key,把返回值放在Set集合中,再遍历Set集合,通过get方法获取每一个key的value

        //获取所有的键,并放在Set集合中Set<String> set = map.keySet();//遍历set,根据所有的键获取值for(String key:set){int value = map.get(key);System.out.println(key + " = " + value);}

通过键值对对象进行遍历

调用entrySet方法,把所有键值对对象放在Set集合中,再遍历Set集合

 可以看出,Entry是Map接口的一个内部接口,所以需要通过Map.Entry的形式调用,也可以直接导入

import java.util.Map.Entry;

就可以省略Map.

遍历时,可以直接打印Entry对象,也可以通过get的方式获取key和value        

        Set<Map.Entry<String, Integer>> entries = map.entrySet();for(Map.Entry<String,Integer> entry : entries){//System.out.println(entry);String s = entry.getKey();Integer i = entry.getValue();System.out.println(s + " = " + i);}

最后还可以通过lambda的形式遍历

        map.forEach(new BiConsumer<String, Integer>() {@Overridepublic void accept(String key, Integer value) {System.out.println(key + " = " + value);}});map.forEach((key, value) -> System.out.println(key + " = " + value));

🍁3.2 LinkedHashMap

和LinkedHashSet一样,LinkedHashMap存储的键是有序的(存储顺序和取出顺序一样)


🍁3.3 TreeMap

TreeMap和TreeSet底层一样,都是红黑树,根据键进行排序,排序规则也是类似的,对于非数值等类型,可以实现Comparable接口,指定比较规则,也可以传入比较器

🍁4. 面试OJ题练习

🍁4.1 随机链表的复制

138. 随机链表的复制

 也就是下面这种情况

如果说直接对链表节点进行复制是不可以的,因为题目中要求的是深拷贝,所以说拷贝后的 节点可能和原来的地址不一样

思路:遍历原来的链表,每遍历一次都创建一个新的节点,把原来的节点和拷贝的新节点的映射关系使用map存储起来,再通过get方法得到节点,再连接next和random

    public Node copyRandomList(Node head) {Map<Node, Node> map = new LinkedHashMap<>();Node cur = head;while (cur != null) {Node copy = new Node(cur.val);map.put(cur, copy);cur = cur.next;}/*cur = head;while (cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}*/Set<Node> keySet = map.keySet();for (Node curNode : keySet) {map.get(curNode).next = map.get(curNode.next);map.get(curNode).random = map.get(curNode.random);}return map.get(head);}

🍁4.2 宝石与石头 

771. 宝石与石头

 这一题就可以很好的利用Set集合元素不能重复的特性了,如果不用Set集合,把全部元素异或一遍就可以找到了,而且速度更快,这里只是为了练习一下Set集合的使用,只需要把jewels存一个set,再遍历stones,判断是否有set集合里的元素即可

public class Text {public static void main(String[] args) {String jewels = "aA";String stones = "aAABBBBB";System.out.println(numJewelsInStones(jewels, stones));}public static int numJewelsInStones(String jewels, String stones) {Set<Character> set = new HashSet<>();for (int i = 0; i < jewels.length(); i++) {set.add(jewels.charAt(i));}int cnt = 0;for (int i = 0; i < stones.length(); i++) {if (set.contains(stones.charAt(i))) {cnt++;}}return cnt;}
}

🍁4.3 前k个高频单词

692. 前K个高频单词

 思路:前k个高频词,就是经典的topk问题,根据之前我们学到的,就是用小根堆解决,首先统计一下每个单词出现的频率,并通过map存储它们的映射关系,接着创建小根堆,套用之前的模板解决

    public List<String> topKFrequent(String[] words, int k) {Map<String, Integer> map = new HashMap<>();//统计单词个数并存入mapfor (String s : words) {if (map.get(s) == null) {map.put(s, 1);} else {int val = map.get(s);map.put(s, ++val);}}//创建根据map的value创建小根堆PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {//相同时根据key创建大根堆,最后反转的时候就可以把字典序靠前的排到前面了if (o1.getValue().compareTo(o2.getValue()) == 0) {return o2.getKey().compareTo(o1.getKey());}return o1.getValue().compareTo(o2.getValue());}});//根据之前讲解的topk问题解决for (Map.Entry<String, Integer> entry : map.entrySet()) {//先把前K个元素加入大根堆if (minHeap.size() < k) {minHeap.offer(entry);} else {Map.Entry<String, Integer> top = minHeap.peek();//堆顶元素频率小于后面的if (top.getValue().compareTo(entry.getValue()) < 0) {minHeap.poll();minHeap.offer(entry);} else if (top.getValue().compareTo(entry.getValue()) == 0) {//堆顶元素等于后面时,堆顶的key字典序大于后面的if (top.getKey().compareTo(entry.getKey()) > 0) {minHeap.poll();minHeap.offer(entry);}}}}ArrayList<String> ans = new ArrayList<>();//把key存入ArrayListfor (int i = 0; i < k; i++) {ans.add(minHeap.poll().getKey());}//题目要求出现频率由高到低,进行翻转Collections.reverse(ans);return ans;}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/397786.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OceanBase V4.2特性解析:MySQL模式下GIS空间表达式的场景及能力解析

1. 背景 1.1. OceanBase Mysql gis空间表达式的应用场景及能力 在OceanBase 4.1版本中&#xff0c;mysql模式下支持了gis数据类型以及部分空间对象相关的表达式&#xff0c;随着客户使用空间数据的需求日益增长&#xff0c;需要快速地补齐空间数据存储和计算分析的能力&#…

实景三维:解锁地理信息新维度,引领未来城市智慧之钥

在这个信息爆炸与科技日新月异的时代&#xff0c;地理信息与遥感技术正以前所未有的速度改变我们认知世界的方式。在推动“实景三维平台”这一前沿科技的构建上&#xff0c;它不仅是地理信息的立体呈现&#xff0c;更是智慧城市的基石&#xff0c;打开了通往未来城市规划、管理…

C++设计模式(代理模式)

1. 电话虫 在海贼中&#xff0c;有一种神奇的通信工具叫做电话虫&#xff08;Den Den Mushi&#xff09;&#xff0c;外形如蜗牛&#xff0c;身上带有斑点或条纹或通体纯色&#xff0c;壳顶上有对讲机或按键&#xff0c;不接通时会睡觉&#xff0c;接通时会惊醒&#xff0c;并发…

数据结构之链表

写在前面 链表是一种常用的线性数据结构&#xff0c;在jdk中也提供具体的实现类java.util.LinkedList。本文来看下其相关内容。 1&#xff1a;链表的特点 链表是一种由很多个节点组成的线性数据结构&#xff0c;每个节点都有一个指向下一个节点的引用&#xff0c;从而构成链…

Unity(2022.3.38LTS) - 下载,安装

目录 A. 简介 B. 下载和安装UnityHub C. 下载安装unity编辑器 安装页面 选择版本 添加模块 D.总结 A. 简介 Unity 是一款广泛使用的跨平台游戏开发引擎。 一、主要特点 跨平台性&#xff1a; 支持多种主流平台&#xff0c;包括 Windows、Mac、Linux、iOS、Android、Xb…

LeetCode_sql_day15(262.行程与用户)

描述&#xff1a;262. 行程和用户 - 力扣&#xff08;LeetCode&#xff09; 取消率 的计算方式如下&#xff1a;(被司机或乘客取消的非禁止用户生成的订单数量) / (非禁止用户生成的订单总数)。 编写解决方案找出 "2013-10-01" 至 "2013-10-03" 期间非禁止…

Vue 应用实例的关键方法与配置案例一

目录 createApp createSSRApp app.mount app.unmount app.component app.directive Vue3.X自定义全局指令 Vue2.X自定义全局指令 app.use app.mixin 非 VIP 用户能够免费下载博文资源 createApp createApp 是 Vue 3.0 中用于创建应用实例的方法。它接收一个…

127. Go反射基本原理

文章目录 反射基础 - go 的 interface 是怎么存储的&#xff1f;iface 和 eface 的结构体定义&#xff08;runtime/iface.go&#xff09;&#xff1a;_type 是什么&#xff1f;itab 是什么&#xff1f; 反射对象 - reflect.Type 和 reflect.Value反射三大定律Elem 方法reflect.…

mysql中select的执行流程

目录 引言 SELECT查询语句的重要性 ​编辑引言部分重写示例&#xff1a; MySQL架构概览 MySQL架构概述 Server层的核心功能模块 知识点图文结合示例&#xff1a; 连接器的作用 连接器的职责 连接器职责 查询缓存的工作原理 查询缓存的概念 查询缓存的工作机制 查询…

虚幻引擎 C++ 实现平面阴影

1、平面阴影介绍 平面阴影是一种相对简单的渲染阴影的方式&#xff0c;可以理解为对一个模型渲染两次&#xff0c;一次是渲染模型本身&#xff0c;另一次是渲染模型的投影。渲染投影可以看作是将模型的顶点变换到地面的投影空间再渲染&#xff0c;可以理解为渲染了一个“压扁”…

Linux内核编程(十二)热插拔

本文目录 一、知识点1. 热插拔概念2. 热插拔机制3. Netlink机制 二、内核发送uevent事件到用户空间1. kobject发送uevent事件2. udevadm命令查看★示例代码&#xff1a;★优化&#xff1a;完善kset_uevent_ops&#xff08;热插拔事件结构体&#xff09; 三、用户空间使用Netlin…

Dubbo源码深度解析(四)

接上篇博客《Dubbo源码深度解析(三)》&#xff0c;上篇博文&#xff0c;主要讲的是DubboBootstrap#start()方法中调用到的其他方法&#xff0c;以及讲到ServiceConfig#export()方法的调用链路。其中讲到最核心的方法为ServiceConfig#doExportUrlsFor1Protocol()&#xff0c;还没…

CentOS7 配置 nginx 和 php 方案

配置方案 一、安装软件二、编写配置文件&#xff0c;连接PHP三、引用文件四、测试 鉴于网上教程错综复杂&#xff0c;写下一这篇文章 本教程只需要三步即可 一、安装软件 yum install -y nginx php php-fpm二、编写配置文件&#xff0c;连接PHP 一般情况下在安装完 nginx 后…

python-质因数分解(赛氪OJ)

[题目描述] 已知正整数 n 是两个不同的质数的乘积&#xff0c;试求出两者中较大的那个质数。输入格式&#xff1a; 输入一个正整数 n。输出格式&#xff1a; 输出一个正整数 p&#xff0c;即较大的那个质数。样例 #1样例输入 #1 21样例输出 #1 7提示&#xff1a; 1≤n≤2109 来…

无字母数字的绕过方法

php代码 <?phpif(isset($_GET[code])){$code $_GET[code];if(strlen($code)>35){die("Long.");}if(preg_match("/[A-Za-z0-9_$]/",$code)){die("NO.");}eval($code);}else{highlight_file(__FILE__);} 题目的限制&#xff1a; webshell…

书籍分享:【矩阵力量】豆瓣评分高达9.6,看完感叹《矩阵论》又白学了

书籍分享&#xff1a;【矩阵力量】豆瓣评分高达9.6&#xff0c;看完感叹《矩阵论》又白学了 《矩阵力量》简要介绍书籍下载链接 《矩阵力量》简要介绍 《矩阵力量》是姜伟生精心编写的线性代数的深度理解之作&#xff0c;作者将抽象的线性代数概念用通俗易懂的语言和大量生动形…

Windows下,C# 通过FastDDS高效通信

目录 1、安装FastDDS 库2、使用IDL定义自己的数据格式3、生成DLL3.1 托管 &#xff08;Managed&#xff09;模式3.2 非托管 &#xff08;Unmanaged&#xff09;模式 -- 可用于Unity 代码示例 eprosima Fast DDS is a C implementation of the DDS (Data Distribution Service) …

vscode用快捷键一键生成vue模板

项目中有些代码模块是固定的&#xff0c;如下面的代码所示&#xff0c;为了不重复写这些相同的代码&#xff0c;我们可以使用快键键一键生成模板。 流程&#xff1a; 中文&#xff1a;首选项-> 用户代码片段 -> 输入框中输入vue,找到vue.json文件&#xff08;没有vue.j…

Vue-07.生命周期

生命周期&#xff1a; 生命周期&#xff1a;指一个对象从创建到销毁的全过程 生命周期的八个阶段&#xff1a;每触发一个阶段&#xff0c;就会自动执行一个生命周期方法&#xff08;钩子方法&#xff09; 状态 阶段周期 beforeCreated 创…

内部排序(插入、交换、选择)

一、排序的部分基本概念 1. 算法的稳定性 若待排序表中有两个元素 Ri 和 Rj &#xff0c;其对应的关键字相同即 keyi keyj&#xff0c;且在排序前 Ri 在 Rj 的前面&#xff0c;若使用某一排序算法排序后&#xff0c;Ri 仍然在 Rj 的前面&#xff0c;则称这个排序算法是稳定的…