devbox
寸_铁
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【Java数据结构】Map和Set（哈希表详解）_java map set

作者：寸_铁 | 2024-08-17 01:52:21

赞

踩

java map set

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关。

目录

1. Map

实例化

添加元素（put）

打印

2. Set

实例化

添加元素（add）

打印

3.  小练习

3.1 找出重复的数据（Set练习）

3.2 去重（Set练习）

3.3 统计重复数据出现的次数（Map练习）

4. LeetCode题型训练

4.1 只出现一次的数字

4.2 ⭐⭐复制带随机指针的链表

4.3 宝石与石头

4.4 坏键盘打字

4.5 前K个高频单词（难题）

1. Map

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

实例化

  1.         Map<String,String> map = new HashMap<>();
  2.         HashMap<String,String> map2 = new HashMap<>();

添加元素（put）

  1.         map.put("猴哥","孙悟空");
  2.         map.put("八戒","猪八戒");
  3.         map.put("悟净","沙僧");

打印

  1. import java.util.Set;
  2.         //1、直接打印法
  3.         System.out.println(map);
  4.  
  5.         //Set打包后再遍历打印法
  6.         Set<Map.Entry<String,String>> set = map.entrySet();
  7.         for (Map.Entry<String, String> entry : set) {
  8.             System.out.println("key："+entry.getKey()+" Value:"+entry.getValue());
  9.         }

2. Set

Set是一个集合类。Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key。

实例化

  1. import java.util.Set;
  2.         Set<Integer> set = new HashSet<>();
  3.         HashSet<Integer> set1 = new HashSet<>();

添加元素（add）

和Map一样也是无序的！

  1.         set1.add(1);
  2.         set1.add(2);
  3.         set1.add(3);
  4.         set1.add(4);
  5.         System.out.println(set1);
  6.         
  7.         set.add("hello");
  8.         set.add("hello1");
  9.         set.add("hello2");
  10.         set.add("hello3");
  11.         set.add("hello4");
  12.         System.out.println(set);

打印

  1.         //1、直接打印
  2.         System.out.println(set);
  3.  
  4.         //2、迭代器(不可以遍历Map)
  5.         Iterator<String> it = set.iterator();
  6.         while (it.hasNext()) {
  7.             System.out.println(it.next());
  8.         }

3.  小练习

  1. 从10W个数据中，找出第一个重复的数据
  2. 去除10W个数据当中，重复的数据（去重）
  3. 统计重复的数据出现的次数

3.1 找出重复的数据（Set练习）

思路：使用set.contains( ) 判断是否已存在于set中

  1.     //判断是否存在set.contains()
  2.     public static void main(String[] args) {
  3.         int[] array = new int[10];
  4.         Random rand = new Random();
  5.         for (int i = 0; i < array.length; i++) {
  6.             array[i] = rand.nextInt(10);
  7.         }
  8.         System.out.println(Arrays.toString(array));
  9.         HashSet<Integer> set = new HashSet<>();
  10.         for (int i = 0; i < array.length; i++) {
  11.             if (set.contains(array[i])) {
  12.                 System.out.println(array[i]);
  13.                 break;
  14.             }
  15.             set.add(array[i]);
  16.         }
  17.         System.out.println(set);
  18.     }

3.2 去重（Set练习）

  1.     //判断是否存在set.contains()
  2.     public static void main(String[] args) {
  3.         int[] array = new int[10];
  4.         Random rand = new Random();
  5.         for (int i = 0; i < array.length; i++) {
  6.             array[i] = rand.nextInt(10);
  7.         }
  8.         System.out.println(Arrays.toString(array));
  9.         HashSet<Integer> set = new HashSet<>();
  10.         for (int i = 0; i < array.length; i++) {
  11.             set.add(array[i]);
  12.         }
  13.         System.out.println(set);
  14.     }

3.3 统计重复数据出现的次数（Map练习）

使用map.contains 和 map.get() == null 都可以用来判断是否已经存在。

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         int[] array = new int[10];
  4.         Random rand = new Random();
  5.         for (int i = 0; i < array.length; i++) {
  6.             array[i] = rand.nextInt(5);
  7.         }
  8.         HashMap<Integer,Integer> map = new HashMap<>();
  9.         //判断数组的数据 是否再map中 没有就是1，有的话就value+1
  10.         for (int i = 0; i < array.length; i++) {
  11.             /*if (map.containsKey(array[i])) {
  12.                 int val = map.get(array[i]);
  13.                 map.put(array[i], val+1);
  14.             } else {
  15.                 map.put(array[i], 1);
  16.             }*/
  17.             if (map.get(array[i] == null)) {
  18.                 map.put(array[i],1);
  19.             } else {
  20.                 int val = map.get(array[i]);
  21.                 map.put(array[i],val+1);
  22.             }
  23.         }
  24.         //打印
  25.         for (Map.Entry<Integer,Integer> entry: map.entrySet()) {
  26.             System.out.println("关键字 "+entry.getKey()+" 次数"+entry.getValue());
  27.         }
  28.     }
  29. }

4. LeetCode题型训练

4.1 只出现一次的数字

136. 只出现一次的数字 - 力扣（LeetCode） (leetcode-cn.com)

常规最优解题法（异或）：

  1. class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         int sum = 0;
  4.         for (int i = 0; i < nums.length; i++) {
  5.             sum ^= nums[i];
  6.         }
  7.         return sum;
  8.     }
  9. }

使用Set：

  1. class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         HashSet<Integer> set = new HashSet<>();
  4.         for (int val : nums) {
  5.             if (set.contains(val)) {
  6.                 set.remove(val);
  7.             } else {
  8.                 set.add(val);
  9.             }
  10.         }
  11.         for (int val : nums) {
  12.             if (set.contains(val)) {
  13.                 return val;
  14.             }
  15.         }
  16.         return -1;
  17.     }
  18. }

4.2 ⭐⭐复制带随机指针的链表

138. 复制带随机指针的链表 - 力扣（LeetCode） (leetcode-cn.com)

  1. class Solution {
  2.     public Node copyRandomList(Node head) {
  3.         HashMap<Node,Node> map = new HashMap<>();
  4.         Node cur = head;
  5.         while (cur != null) {
  6.             Node node = new Node(cur.val);
  7.             map.put(cur,node);
  8.             cur = cur.next;
  9.         }
  10.         cur = head;
  11.         while (cur != null) {
  12.             map.get(cur).next = map.get(cur.next);
  13.             map.get(cur).random = map.get(cur.random);
  14.             cur = cur.next;
  15.         }
  16.         return map.get(head);
  17.     }
  18. }

4.3 宝石与石头

771. 宝石与石头 - 力扣（LeetCode） (leetcode-cn.com)

  1. class Solution {
  2.     public int numJewelsInStones(String jewels, String stones) {
  3.         HashSet<Character> set = new HashSet<>();
  4.         for (int i = 0; i < jewels.length(); i++) {
  5.             char ch = jewels.charAt(i);
  6.             set.add(ch);
  7.         }
  8.         int count = 0;
  9.         for (int i = 0; i < stones.length(); i++) {
  10.             char ch = stones.charAt(i);
  11.             if (set.contains(ch)) {
  12.                 count++;
  13.             }
  14.         }
  15.         return count;
  16.     }
  17. }

4.4 坏键盘打字

旧键盘 (20)__牛客网 (nowcoder.com)

思路：

  1. 把str1当中的每个字符，转换成大写的，然后放到集合当中（char[ ]  ch=str1.toUpperCase().toCharArray() ;
  2. 遍历str1，每个字符仍然要是大写，和集合当中的元素去比较，没有就输出
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void func(String str1, String str2) {
  5.         HashSet<Character> set = new HashSet<>();
  6.         //把打印出来的东西放进set
  7.         for (char ch : str2.toUpperCase().toCharArray()) {
  8.             set.add(ch);
  9.         }
  10.         for (char ch : str1.toUpperCase().toCharArray()) {
  11.             if (!set.contains(ch)) {
  12.                 System.out.print(ch);
  13.                 set.add(ch);
  14.             }
  15.         }
  16.     }
  17.     public static void main(String[] args) {
  18.         Scanner sc = new Scanner(System.in);
  19.         String str1 = sc.nextLine();
  20.         String str2 = sc.nextLine();
  21.         func(str1,str2);
  22.     }
  23. }

4.5 前K个高频单词（难题）

692. 前K个高频单词 - 力扣（LeetCode） (leetcode-cn.com)

思路：

  1. 统计字符串当中每个单词出现的次数（HashMap）
  2. 定义一个小根堆，设置其比较方式是根据每个单词出现的次数进行比较
  3. 开始遍历map，拿到每一个entry
  1. class Solution {
  2.     public List<String> topKFrequent(String[] words, int k) {
  3.         //1、统计单词出现的次数 存放在map当中
  4.         HashMap<String,Integer> map = new HashMap<>();
  5.         for (String s : words) {
  6.             if (map.get(s) == null) {
  7.                 map.put(s,1);
  8.             } else {
  9.                 int val = map.get(s);//原来这个单词出现的次数
  10.                 map.put(s,val+1);
  11.             }
  12.         }
  13.  
  14.         //定义一个小根堆，因为我们找的是出现频率高的，所以小根堆的比较方式是根据每个单词出现的次数进行比较
  15.     PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>() {
  16.         @Override
  17.         public int compare(Map.Entry<String,Integer> o1, Map.Entry<String,Integer> o2) {
  18.             if(o1.getValue().compareTo(o2.getValue()) == 0) {
  19.                 return o2.getKey().compareTo(o1.getKey());
  20.             }
  21.             return o1.getValue()-o2.getValue();
  22.         }
  23.     });
  24.  
  25.         //3、开始遍历map，拿到每一个entry
  26.         for (Map.Entry<String,Integer> entry : map.entrySet()) {
  27.             if (minHeap.size() < k ) {
  28.                 minHeap.offer(entry);
  29.             } else {
  30.                 Map.Entry<String,Integer> top = minHeap.peek();
  31.                 if (top != null) {
  32.                     if (top.getValue().compareTo(entry.getValue()) == 0) {
  33.                         if (entry.getKey().compareTo(top.getKey()) < 0) {
  34.                             minHeap.poll();
  35.                             minHeap.offer(entry);
  36.                         }
  37.                     } else {
  38.                         if (entry.getValue().compareTo(top.getValue()) > 0) {
  39.                             minHeap.poll();
  40.                             minHeap.offer(entry);
  41.                         }
  42.                     }
  43.                 }
  44.             }
  45.         }
  46.  
  47.         //4、小堆弹出信息
  48.         List<String> ret = new ArrayList<>();
  49.         for (int i = 0; i < k; i++) {
  50.             Map.Entry<String,Integer> top = minHeap.poll();
  51.             if (top != null) {
  52.                 ret.add(top.getKey());
  53.             }
  54.         }
  55.         Collections.reverse(ret);
  56.         return ret;
  57.     }
  58. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/990683
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号