数据结构 Java数据结构 --- Map和Set

文章目录

Map 和 Set

1. Map

1.1 关于Map的说明

Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

1.2 Map 的常用方法说明

方法解释V get(Object key)返回 key 对应的 valueV getOrDefault(Object key, V defaultValue)返回 key 对应的 value，key 不存在，返回默认值V put(K key, V value)设置 key 对应的 valueV remove(Object key)删除 key 对应的映射关系Set< K> keySet()返回所有 key 的不重复集合Collection< V> values()返回所有 value 的可重复集合Set<Map.Entry<K, V>> entrySet()返回所有的 key-value 映射关系boolean containsKey(Object key)判断是否包含 keyboolean containsValue(Object value)判断是否包含 value

1.3 关于Map.Entry< K, V >的说明

Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式
方法解释K getKey()返回 entry 中的 keyV getValue()返回 entry 中的 valueV setValue(V value)将键值对中的value替换为指定value
例:

publicstaticvoidmain(String[] args){Map<String,Integer> map =newHashMap<>();
        map.put("a",3);
        map.put("h",5);
        map.put("b",4);Set<Map.Entry<String,Integer>> entrySet =  map.entrySet();for(Map.Entry<String,Integer> entry : entrySet){System.out.println(entry.getKey()+"->"+entry.getValue());}}

1.4 Map的注意事项

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2. Map中存放键值对的Key是唯一的，value是可以重复的
3. 在Map中插入键值对时，key不能为空，否则就会抛NullPointerException异常，但是value可以为空.(HashMap可以)
4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

1.5 TreeMap和HashMap的区别

Map底层结构TreeMapHashMap底层结构红黑树哈希桶插入/删除/查找时间复杂度O(logN)O(1)是否有序关于Key有序无序线程安全不安全不安全插入/删除/查找区别需要进行元素比较通过哈希函数计算哈希地址比较与覆写key必须能够比较，否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法应用场景需要Key有序场景下Key是否有序不关心，需要更高的时间性能

2. Set

2.1 常见方法说明

方法解释boolean add(E e)添加元素，但重复元素不会被添加成功void clear()清空集合boolean contains(Object o)判断 o 是否在集合中Iterator< E> iterator()返回迭代器boolean remove(Object o)删除集合中的 oint size()返回set中元素的个数boolean isEmpty()检测set是否为空，空返回true，否则返回falseObject[] toArray()将set中的元素转换为数组返回boolean containsAll(Collection<?> c)集合c中的元素是否在set中全部存在，是返回true，否则返回falseboolean addAll(Collection<? extendsE> c)将集合c中的元素添加到set中，可以达到去重的效果
例:

publicstaticvoidmain(String[] args){Set<Integer> set =newHashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);Iterator<Integer> iterator = set.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}}

2.2 Set的注意事项

1. Set是继承自Collection的一个接口类
2. Set中只存储了key，并且要求key一定要唯一
3. Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
4. Set最大的功能就是对集合中的元素进行去重
5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
7. Set中不能插入null的key

2.3 TreeSet和HashSet的区别

Set底层结构TreeSetHashSet底层结构红黑树哈希桶插入/删除/查找时间复杂度O(logN)O(1)是否有序关于Key有序不一定有序线程安全不安全不安全插入/删除/查找区别按照红黑树的特性来进行插入和删除1. 先计算key哈希地址 2. 然后进行插入和删除比较与覆写 key必须能够比较，否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法应用场景需要Key有序场景下Key是否有序不关心，需要更高的时间性能

3. 面试题练习

第一题: 只出现一次的数字

LeetCode 136: 只出现一次的数字
描述:
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:

解题思路:

1. 把数组放入Set集合中.因为Set中key是唯一的.
2. 如果元素不在Set中,就添加元素到Set中.
3. 如果元素在Set中,就删除该元素.
4. 遍历结束,返回Set集合中的内容.

代码实现:

classSolution{publicintsingleNumber(int[] nums){Set<Integer> set =newHashSet<>();for(int val : nums){if(!set.contains(val)){
                set.add(val);//Set中没有val就添加val到set中}else{
                set.remove(val);//set中有val就删除set中的val}}//遍历结束,返回set中的元素return set.iterator().next();}}

第二题: 复制带随机指针的链表

LeetCode 138: 复制带随机指针的链表
描述:
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有

X

和

Y

两个节点，其中

X.random --> Y

。那么在复制链表中对应的两个节点

x

和

y

，同样有

x.random --> y 。

返回复制链表的头节点。
用一个由

n

个节点组成的链表来表示输入/输出中的链表。每个节点用一个

[val, random_index]

表示：

val: 一个表示 Node.val 的整数。
random_index: 随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点

head

作为传入参数。

解题思路:

1. 第一次遍历链表,将 老节点 和 新节点 放入 Map中.
2. 第二次遍历链表,通过get方法得到新老节点来修改新节点的next和random
3. map.get(cur).next = map.get(cur.next) 链接新节点的next
4. map.get(cur).random = map.get(cur.random) 链接新节点的random
5. 遍历结束,返回map.get(head)

代码实现:

classSolution{publicNodecopyRandomList(Node head){Map<Node,Node> map =newHashMap<>();Node cur = head;// 第一次遍历while(cur !=null){Node node =newNode(cur.val,null,null);
            map.put(cur,node);//存储新老节点之间的映射
            cur = cur.next;}
        cur = head;// 第二次遍历while(cur !=null){
            map.get(cur).next = map.get(cur.next);//修改next
            map.get(cur).random = map.get(cur.random);//修改random
            cur = cur.next;}return map.get(head);//返回新节点的头节点       }}

第三题: 宝石与石头

LeetCode 771: 宝石与石头
描述:
给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。

解题思路:

1. 遍历字符串jewels将所有字符放入Set集合中.
2. 遍历字符串stones,判断是否字符在Set集合中,如果在就count++;
3. 返回count即可;

代码实现:

classSolution{publicintnumJewelsInStones(String jewels,String stones){Set<Character> set =newHashSet<>();//遍历jewels 将字符放入到ch中for(Character ch:jewels.toCharArray()){
            set.add(ch);}int count =0;//遍历stones 判断set中是否有该字符,如果有就count++for(Character ch:stones.toCharArray()){if(set.contains(ch)) count++;}return count;}}

第四题: 坏键盘打字

牛客 : 旧键盘 (20)
描述:
旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出
肯定坏掉的那些键。

解题思路:

1. 分别用except和real接收实际输入和应该输入的字符串.
2. 将两个字符串都变成大写.
3. 遍历real字符串,将字符放入set集合中
4. 遍历except字符串,如果字符在set集合中没有就输出,并放入set1集合中.在每次判断的时候多判断一次.字符也不在set1集合中.

代码实现:

importjava.util.*;publicclassMain{publicstaticvoidmain(String[] args){Scanner sc =newScanner(System.in);// 将输入的内容大写String expect = sc.nextLine().toUpperCase();String real = sc.nextLine().toUpperCase();Set<Character> set =newHashSet<>();// 将real字符串的内容放入set集合中for(Character ch:real.toCharArray()){
            set.add(ch);}// set1集合用来放坏的键盘的字符Set<Character> set1 =newHashSet<>();for(Character ch:expect.toCharArray()){// 判断两次 以防止多次输出相同的字符if(!set.contains(ch)&&!set1.contains(ch)){System.out.print(ch);
                set1.add(ch);}}}}

第五题: 前K个高频单词

LeetCode 692: 前K个高频单词
描述:
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

解题思路:

1. 先用 Map 记录每个单词出现的次数
2. 再建立一个大小为k的小根堆.按照题目规定 来写Comparator
3. 遍历Map,当堆小于k的时候,直接入堆.当大于k的时候

• 如果堆顶元素出现的次数比当前元素的出现次数小,就出堆顶元素,将当前元素入堆.
• 如果堆顶元素出现的次数等于当前元素出现的次数,且按字典顺序在前面时,就出堆顶元素,将当前元素入堆

1. 最后循环堆,直到堆为空,每次将堆顶元素poll(),并放入到list的0下标处(相当于头插)

代码实现:

classSolution{publicList<String>topKFrequent(String[] words,int k){Map<String,Integer> map =newHashMap<>();//建立大小为k的小根堆PriorityQueue<Map.Entry<String,Integer>> queue =newPriorityQueue<>(k,newComparator<Map.Entry<String,Integer>>(){@Overridepublicintcompare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){if(o1.getValue().equals(o2.getValue())){//这里是出现次数相同时,根据字典顺序存放的规则return o2.getKey().compareTo(o1.getKey());}else{//这里是根据出现次数存放的规则return o1.getValue()- o2.getValue();}}});// 记录每个单词出现的次数for(String str:words){
            map.put(str,map.getOrDefault(str,0)+1);}//遍历mapfor(Map.Entry<String,Integer> entry:map.entrySet()){if(queue.size()< k){//大小小于k时,直接入堆
                queue.offer(entry);}else{Map.Entry<String,Integer> top = queue.peek();// 分为堆顶元素出现次数相同 和 堆顶元素出现次数小于当前元素的情况 if(top.getValue().compareTo(entry.getValue())==0){//当出现次数相同时,把字典顺序在前的放入堆中,在后的不用管if(top.getKey().compareTo(entry.getKey())>0){
                        queue.poll();
                        queue.offer(entry);}}elseif(top.getValue().compareTo(entry.getValue())<0){
                    queue.poll();
                    queue.offer(entry);}}}//将堆中元素存放在list中List<String> list =newArrayList<>();while(!queue.isEmpty()){
            list.add(0,queue.poll().getKey());//按照头插法}return list;}}