Map和Set及其背后二叉搜索树的数据结构

转x33g5p2x  于2022-02-07 转载在 其他  
字(15.1k)|赞(0)|评价(0)|浏览(368)

在这篇博客当中介绍红黑树是因为TreeSet与TreeMap的底层数据结构是红黑树，而红黑树的基础是搜索树。虽然本章不讲红黑树，但是最为一个基础来了解。

一、二叉搜索树

在二叉搜索树类当中定义一个内部类Node，说明二叉搜索树是由结点构成的。

  1. public static class Node {
  2.         public int val;
  3.         public Node left;
  4.         public Node right;
  6.         public Node (int val) {
  7.             this.val = val;
  8.         }
  9.     }

1.二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

  1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  3. 它的左右子树也分别为二叉搜索树
  4. 二叉搜索树的中序遍历是有序的。

2.二叉搜索树的查找

因为二叉搜索树中的左结点比根结点的值小，右结点比根节点的值大，则从根开始遍历，如果比根结点的值小，则向左走；反之向右走。
代码：

  1. public Node search(int key) {
  2.         Node cur = root;
  3.         while (cur != null) {
  4.             if(cur.val == key) {
  5.                 return cur;
  6.             }else if(cur.val < key) {
  7.                 cur = cur.right;
  8.             }else {
  9.                 cur = cur.left;
  10.             }
  11.         }
  12.         return null;
  13.     }

二叉搜索树的查找效率：

若在最好情况下，即根节点在左右树的中间并且左右子树都平衡。查找的时间复杂度为O(log2^N) 。因此最好的情况下该二叉搜索树是一个完全二叉树。
如：

若在最坏情况下，即根结点没有左子树或没有右子树。查找的时间复杂度为O(N) 。
如：

3.二叉搜索树的插入

二叉搜索树的插入不是为了存储，是为了满足二叉搜索树的性质。因此如果有一个值与二叉搜索树当中的某个结点的值相同，则不再存储。

需要注意的是，当我们正常遍历到一个合适的位置放入某个结点的值时，我们要的是上一个结点的左或者右结点放入该结点。如：

因为7比5大，则往右走。

因为7比8小，则往左走。

因为7比6大，往右走。此时发现root为空。因此root的位置就是该结点应该放入的位置。但是无法得到值为6的结点。因此要设置一个前驱结点来记录前面一个结点的位置。如果root已经为空，则放入的位置就应该由前驱结点判断它的值是否比前驱结点大，大则放右边，小则放左边。

  1. public boolean insert(int key) {
  2.         Node node = new Node(key);
  3.         if(root == null) {
  4.             root = node;
  5.             return true;
  6.         }
  8.         Node cur = root;
  9.         Node parent = null;
  11.         while(cur != null) {
  12.             if(cur.val == key) {
  13.                 return false;
  14.             }else if(cur.val < key) {
  15.                 parent = cur;
  16.                 cur = cur.right;
  17.             }else {
  18.                 parent = cur;
  19.                 cur = cur.left;
  20.             }
  21.         }
  22.         //parent
  23.         if(parent.val > key) {
  24.             parent.left = node;
  25.         }else {
  26.             parent.right = node;
  27.         }
  28.         return true;
  29.     }

4.二叉搜索树的删除(难点)

二叉搜索树如果要删除结点，有很多种情况。

首先来看第一种大情况。
设待删除的结点为cur，待删除的双亲结点为parent。

cur.left为空是大前提。
第一种小情况：
因为cur在根结点处，删除cur结点则根应该为cur结点的右节点。

第二种小情况：
cur结点是parent结点的左节点，则要删除cur结点时有parent.left = cur.right;。

第三种小情况：
cur结点是parent结点的右节点，则有parent.right = cur.right;

第二种大情况：

第一种小情况：
当cur为根时，并且cur.left为空，有root = cur.left;

第二种小情况：
当cur为parent的左节点时，有parent.left = cur.left;

第三种小情况：
当cur为parent的右节点时，则有parent.right = cur.left;

第三种大情况：

第一种小情况：
因为要删除cur结点，可以采用**“替罪羊”**的方式删除cur的值的结点，但不是直接删除cur的结点。

有两种找替罪羊的方法：
1.在待删除结点的右树的最左边的结点与待删除的结点的值交换。
2.在待删除结点的左树的最右边的结点与待删除的结点的值交换。

以下图为例：

我们可以设立两个标记：target和targetParent。以找cur结点的右树的最左结点为例，初始位置令targetParent指向cur，而target指向cur.right。遍历该子树的左树，当taget.left不为空时，证明找到了替罪羊。

初始：tp代表targetParent，t代表target。

先令tp指向t的位置，再将t向左遍历。此时t.left为空。

t.left为空时将t的值与cur的值交换，这样就转变上面第一种大情况下的t.left==null的问题，因此有tp.left=t.right。因为已经确定了t就是该子树的最左边结点。

第二种小情况：

因为t已经是cur.right的最左边的结点，因此若采用第一种小情况下的tp.left=t.right是不符合的。因此这种情况下只要将t的值与cur的值交换后，有tp.right=t.right即可。

  1. public void remove(Node parent,Node cur) {
  2.         if(cur.left == null) {
  3.             if(cur == root) {
  4.                 root = cur.right;
  5.             }else if(cur == parent.left) {
  6.                 parent.left = cur.right;
  7.             }else {
  8.                 parent.right = cur.right;
  9.             }
  10.         }else if(cur.right == null) {
  11.             if(cur == root) {
  12.                 root = cur.left;
  13.             }else if(cur == parent.left) {
  14.                 parent.left = cur.left;
  15.             }else {
  16.                 parent.right = cur.left;
  17.             }
  18.         }else {
  19.             Node targetParent =  cur;
  20.             Node target = cur.right;
  21.             while (target.left != null) {
  22.                 targetParent = target;
  23.                 target = target.left;
  24.             }
  25.             cur.val = target.val;
  26.             if(target == targetParent.left) {
  27.                 targetParent.left = target.right;
  28.             }else {
  29.                 targetParent.right = target.right;
  30.             }
  31.         }
  32.     }
  34.     public void removeKey(int key) {
  35.         if(root == null) {
  36.             return;
  37.         }
  38.         Node cur = root;
  39.         Node parent = null;
  40.         while (cur != null) {
  41.             if(cur.val == key) {
  42.                 remove(parent,cur);
  43.                 return;
  44.             }else if(cur.val < key){
  45.                 parent = cur;
  46.                 cur = cur.right;
  47.             }else {
  48.                 parent = cur;
  49.                 cur = cur.left;
  50.             }
  51.         }
  52.     }

5.二叉搜索树的基本操作代码汇总

  1. class BinarySearchTree {
  3.     public static class Node {
  4.         public int val;
  5.         public Node left;
  6.         public Node right;
  8.         public Node (int val) {
  9.             this.val = val;
  10.         }
  11.     }
  13.     public Node root;
  15.     /**
  16.      * 查找
  17.      * @param key
  18.      */
  19.     public Node search(int key) {
  20.         Node cur = root;
  21.         while (cur != null) {
  22.             if(cur.val == key) {
  23.                 return cur;
  24.             }else if(cur.val < key) {
  25.                 cur = cur.right;
  26.             }else {
  27.                 cur = cur.left;
  28.             }
  29.         }
  30.         return null;
  31.     }
  33.     /**
  34.      *
  35.      * @param key
  36.      * @return
  37.      */
  38.     public boolean insert(int key) {
  39.         Node node = new Node(key);
  40.         if(root == null) {
  41.             root = node;
  42.             return true;
  43.         }
  45.         Node cur = root;
  46.         Node parent = null;
  48.         while(cur != null) {
  49.             if(cur.val == key) {
  50.                 return false;
  51.             }else if(cur.val < key) {
  52.                 parent = cur;
  53.                 cur = cur.right;
  54.             }else {
  55.                 parent = cur;
  56.                 cur = cur.left;
  57.             }
  58.         }
  59.         //parent
  60.         if(parent.val > key) {
  61.             parent.left = node;
  62.         }else {
  63.             parent.right = node;
  64.         }
  66.         return true;
  67.     }
  69.     public void remove(Node parent,Node cur) {
  70.         if(cur.left == null) {
  71.             if(cur == root) {
  72.                 root = cur.right;
  73.             }else if(cur == parent.left) {
  74.                 parent.left = cur.right;
  75.             }else {
  76.                 parent.right = cur.right;
  77.             }
  78.         }else if(cur.right == null) {
  79.             if(cur == root) {
  80.                 root = cur.left;
  81.             }else if(cur == parent.left) {
  82.                 parent.left = cur.left;
  83.             }else {
  84.                 parent.right = cur.left;
  85.             }
  86.         }else {
  87.             Node targetParent =  cur;
  88.             Node target = cur.right;
  89.             while (target.left != null) {
  90.                 targetParent = target;
  91.                 target = target.left;
  92.             }
  93.             cur.val = target.val;
  94.             if(target == targetParent.left) {
  95.                 targetParent.left = target.right;
  96.             }else {
  97.                 targetParent.right = target.right;
  98.             }
  99.         }
  100.     }
  102.     public void removeKey(int key) {
  103.         if(root == null) {
  104.             return;
  105.         }
  106.         Node cur = root;
  107.         Node parent = null;
  108.         while (cur != null) {
  109.             if(cur.val == key) {
  110.                 remove(parent,cur);
  111.                 return;
  112.             }else if(cur.val < key){
  113.                 parent = cur;
  114.                 cur = cur.right;
  115.             }else {
  116.                 parent = cur;
  117.                 cur = cur.left;
  118.             }
  119.         }
  120.     }
  124. }
  125. public class TestDemo {
  127.     public static void inorder(BinarySearchTree.Node root) {
  128.         if(root == null) {
  129.             return;
  130.         }
  131.         inorder(root.left);
  132.         System.out.print(root.val+" ");
  133.         inorder(root.right);
  134.     }
  136.     public static void main(String[] args) {
  137.         BinarySearchTree binarySearchTree = new BinarySearchTree();
  138.         binarySearchTree.insert(13);
  139.         binarySearchTree.insert(1);
  140.         binarySearchTree.insert(21);
  141.         binarySearchTree.insert(14);
  142.         binarySearchTree.insert(5);
  143.         binarySearchTree.insert(6);
  145.         inorder(binarySearchTree.root);
  146.         System.out.println();//1 5 6 13 14 21 
  148.         System.out.println(binarySearchTree.search(1).val);//1
  150.         binarySearchTree.removeKey(13);
  152.         inorder(binarySearchTree.root);
  153.         System.out.println();//1 5 6 14 21
  154.     }
  155. }

二、集合Map的使用

1.关于Map的说明

Map在Java当中不被Collection实现，它是单独的一个接口，因此当要打印Map类型当中的元素时，不能使用迭代器打印。

该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

2.Map集合中常用的方法说明

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

注意：

  1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
  2. Map中存放键值对的Key是唯一的，若再次put相同的Key的Value值，则Value会更新。
  3. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
  4. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
  5. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
  6. 打印map的时候打印的顺序可能不是按照put的顺序进行打印的。

3.Map中方法的详细说明

对于方法中的细节有：
1.调用getOrDefault方法时有Key则返回Key的Value值，没有Key则返回的是调用getOrDefault方法设置的默认的Value值。
2.调用put方法时Key和Value值都可以设置为null。
3.调用keySet()方法与values()。打印方式与结果

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         Map<String,String> map = new HashMap<>();
  4.         map.put("及时雨1","宋江1");
  5.         map.put("及时雨2","宋江2");
  6.         Set<String> strings = map.keySet();
  7.         System.out.println(strings);//[及时雨2, 及时雨1]
  8.         Collection<String> collections = map.values();
  9.         System.out.println(collections);//[宋江2, 宋江1]
  10.     }
  11. }

4.entrySet()方法的返回值类型是Set<Map.Entry<K, V>>，表面它是一个集合，集合里面的类型是键值对。

若一个变量是Map.Entry<K, V>类型，则它能够拿到该类型的Key值或者Value值。

有关于Map.Entry<K, V>类型的说明：
Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式。

方法解释
K getKey()返回 entry 中的 key
V getValue()返回 entry 中的 value
V setValue(V value)将键值对中的value替换为指定value

注意：Map.Entry<K,V>并没有提供设置Key的方法。

因此，有关于Map中entrySet的方法细节：

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         Map<String,String> map = new HashMap<>();
  4.         map.put("及时雨1","宋江1");
  5.         map.put("及时雨2","宋江2");
  6.         Set<Map.Entry<String,String>> entrySet = map.entrySet();
  7.         System.out.println(entrySet);
  8.         System.out.println("======");
  9.         for (Map.Entry<String,String> entry:entrySet) {
  10.             System.out.println("key: "+entry.getKey()+" value: "+entry.getValue());
  11.         }
  12.     }
  13. }
  14. //打印结果
  15. [及时雨2=宋江2, 及时雨1=宋江1]
  16. ======
  17. key: 及时雨2 value: 宋江2
  18. key: 及时雨1 value: 宋江1

5.TreeMap和HashMap的区别

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

三、集合Set的使用

Set与Map主要的不同有两点：
1、Set是继承自Collection的接口类。
2、Set中只存储了Key。

1.Set集合中常用的方法说明

方法解释
boolean add(E e)添加元素，但重复元素不会被添加成功
void clear()清空集合
boolean contains(Object o)判断 o 是否在集合中
Iterator< E> iterator()返回迭代器
boolean remove(Object o)删除集合中的 o
int size()返回set中元素的个数
boolean isEmpty()检测set是否为空，空返回true，否则返回false
Object[] toArray()将set中的元素转换为数组返回
boolean containsAll(Collection<?> c)集合c中的元素是否在set中全部存在，是返回true，否则返回false
boolean addAll(Collection<? extends E> c)将集合c中的元素添加到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. TreeSet和HashSet的区别
Set底层结构TreeSetHashSet
底层结构红黑树哈希桶
插入/删除/查找时间复杂度O(log2^N)O(1)
是否有序关于Key有序不一定有序
线程安全不安全不安全
插入/删除/查找区别按照红黑树的特性来进行插入和删除1. 先计算key哈希地址 2. 然后进行插入和删除
比较与覆写key必须能够比较，否则会抛出ClassCastException异常自定义类型需要覆写equals和hashCode方法
应用场景需要Key有序场景下Key是否有序不关心，需要更高的时间性能

2.Set集合中方法的详细说明

1.Set中不存在相同的Key，即使调用add方法添加了相同的Key，打印的Set里面也只会含有一个Key值。

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         Set<String> set = new HashSet<>();
  4.         set.add("zjr");
  5.         set.add("zjr1");
  6.         set.add("zjr1");
  7.         System.out.println(set);//[zjr, zjr1]
  8.     }
  9. }

2.调用Set集合中的迭代器，返回的类型是Iterator< E>。则迭代器能够打印set里面的元素。

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         Set<String> set = new HashSet<>();
  4.         set.add("zjr");
  5.         set.add("zjr1");
  6.         Iterator<String> iterator = set.iterator();
  7.         while(iterator.hasNext()) {
  8.             System.out.println(iterator.next());
  9.         }
  10.     }
  11. }

3.调用Set集合的toArray方法，它的返回值类型是Object[]，因为在Java当中数组不能够整体强转，因此只能用Object[]类型的数组去接收。

四、有关Map与Set的基础题

1.有10w个数据，如何找到第一个重复的数据？
思路：因为Set能够去除重复的元素，因此将一个个元素依次添加到Set后，每添加一次前判断是否包含该元素，如果是第一次包含的直接返回该元素。

  1. public static void main5(String[] args) {
  2.         ArrayList<Integer> list = new ArrayList<>();
  3.         Random random = new Random();
  4.         for (int i = 0; i < 10_0000; i++) {
  5.             list.add(random.nextInt(10000));
  6.         }
  8.         HashSet<Integer> set = new HashSet<>();
  10.         for (int i = 0; i < list.size(); i++) {
  11.             if(set.contains(list.get(i))) {
  12.                 System.out.println(list.get(i));
  13.                 break;
  14.             }else {
  15.                 set.add(list.get(i));
  16.             }
  17.         }
  18.     }

2.有10w个数据，如何去除掉所有重复的数据？
思路：因为Set集合当中不包含重复的元素，并且能够自动去除重复的元素，因此将10w个数据添加到Set集合当中则能够去掉所有重复的数据。

  1. public static void main(String[] args) {
  2.         ArrayList<Integer> list = new ArrayList<>();
  3.         Random random = new Random();
  4.         for (int i = 0; i < 10_0000; i++) {
  5.             list.add(random.nextInt(10000));
  6.         }
  8.         HashSet<Integer> set = new HashSet<>();
  9.         for (int i = 0; i < list.size(); i++) {
  10.             set.add(list.get(i));
  11.         }
  12.         System.out.println(set);
  13.     }

3.有10w个数据，如何统计每个数据出现了多少次？
思路：因为Map集合中能够将每个Key值对应一个Value值，因此利用Map能够记录每个元素出现了多少次。

  1. public static void main(String[] args) {
  2.         ArrayList<Integer> list = new ArrayList<>();
  3.         Random random = new Random();
  4.         for (int i = 0; i < 10_0000; i++) {
  5.             list.add(random.nextInt(10000));
  6.         }
  7.         //        数据    次数
  8.         HashMap<Integer,Integer> map = new HashMap<>();
  9.         for (Integer key : list) {
  10.             if(map.get(key) == null) {
  11.                 map.put(key,1);
  12.             }else {
  13.                 //说明之前存储过
  14.                 int count = map.get(key);
  15.                 map.put(key,count+1);
  16.             }
  17.         }
  19.         for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
  20.             if(entry.getValue() > 1) {
  21.                 System.out.println("重复的数据: "+entry.getKey() +"出现的次数 : "+entry.getValue());
  22.             }
  23.         }
  24.     }

五、有关Map与Set的面试题

1.只出现一次的数字

对应leetcode题

思路：
第一种：跟上面的基础面试题中统计每个数据出现多少次的道理相似，将所有元素用Map记录，所有元素都添加到Map后，则找到Value为1的数字，返回即可。

第二种：跟上面基础面试题中返回第一个出现的元素相似，将每个元素依次添加到Set中，添加前先判断是否有元素已经在Set中，若有则将Set中已有的元素用remove方法删除。最后Set当中只剩一个只出现一次的数字。

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

2.复制带随机指针的链表

对应leetcode题

思路：题目要求复制链表中的指针都不应指向原链表中的节点，因此不能直接复制原链表中的结点，否则会指向原链表中的结点。

因此可以利用Map中的每一个Key对应一个Value的原理，第一个结点对应的是复制的新的第一个结点，第二个结点对应的是复制的第二个结点，以此类推。

首先用cur指向第一个结点，当cur不为空，就创建一个结点，将val值复制到结点当中，并且设置Map第一个结点对应的是创建的第一个结点以此类推。这个是第一次遍历原链表。

第二次遍历原链表，目的是将创建的新的结点的next与random域指向与原链表的对应的位置。

如：下图为原链表，则复制的链表也要为是这种结构。

第一次遍历后有Map：

因此第二次遍历原链表时有map.get(cur).next=map.get(cur.next);与map.get(cur).random=map.get(cur.random);，map.get(cur)拿到的是Map中对应的新的结点，map.get(cur.next)拿到的是Map当中cur.next的对应的新的结点。random域也是同样的道理。

代码：

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

3.宝石与石头

对应leetcode题

思路：因为给了两个字符串，并且判断石头里面是否有宝石。只需要将石头里面的字符串去重（用到Set集合）并且用计数器记录石头与宝石的字符有多少个是相同的即可。

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

4.坏键盘打字

对应牛客题

< br/>指的是换行。

7_This_is_a_test 与
_hs_s_a_es 对比少了什么

少了7Ti，但是输出的要大写，并且按照先少的顺序打印。

思路：首先将第一个输入的字符串全部变为大写并且转为字符数组存入Set set1集合当中，从头开始遍历第二个输入的字符串，如果set1中没有该字符，则将该字符添加到set2中。set2的设置是避免重复的打印，因此也要判断set2中是否有该字符。set1与set2中都没有该字符则可以打印。

set1中有该字符则说明该键是好的，set2中没有该字符则避免重复的打印。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         String str1 = scan.nextLine();
  7.         String str2 = scan.nextLine();
  8.         Set<Character> set = new HashSet<>();
  9.         for(char ch:str2.toUpperCase().toCharArray()) {
  10.             set.add(ch);
  11.         }
  12.         Set<Character> set2 = new HashSet<>();
  13.         for(char ch:str1.toUpperCase().toCharArray()) {
  14.             if(!set.contains(ch)&&!set2.contains(ch)) {
  15.                 set2.add(ch);
  16.                 System.out.print(ch);
  17.             }
  18.         }
  19.     }
  20. }

5.前k个高频单词

对应leetcode题

思路：看到题目，首先想到的是topK问题，又因为找前k个出现次数最多的单词，则创建的是小堆。

观察示例1：如果找前k个次数最多的，并且出现次数相同时，输出的顺序是字母顺序。

观察示例2：如果找前k个次数最多的，并且出现次数不相同时，输出的顺序是出现的次数由高到低。

步骤：
1、首先一定是创建一个Map来记录每个单词出现的次数。再遍历字符串数组在Map中找到对应的Map.Entry<String,Integer>类型创建小堆，当有字符串出现的次数比堆顶多时，堆顶的元素要出堆，而遍历到的字符串的Map.Entry<String,Integer>类型要进堆。

2、小堆的顺序一定是从小到大的排序，而最后输出的是从大到小的排序，并且方法的返回值类型为List< String>，因此我们可以将最后的list倒序存放。

3、而单单比较字符串的出现的次数还不够，因为示例一中提到出现次数相同时要按照首字母的大小顺序输出。因此我们将堆的创建改为：当字符串出现的次数不同时，按照小堆创建堆，则出现次数最少的放在最前面；当字符串比较的出现相同时，按照大堆创建堆，则首字母最大的放在最前面。这种操作的主要原因是最后存放到List< String>当中可以逆序，逆序后能够满足示例1与示例2。

4、因为堆中的元素的类型都是Map.Entry<String,Integer>类型，而方法的返回值是List< String>,因此可以遍历堆中的元素，调用getKey方法获取Map.Entry<String,Integer>中的String类型的数据。因为此时堆是按照出现次数由低到高存放的，首字母由大到小存放的；因此将对应的字符串存入List< String>当中后调用Collections集合中的reverse方法逆置list。

注意：对堆顶元素操作前要判断该堆顶元素是否为空。

  1. class Solution {
  2.     public List<String> topKFrequent(String[] words, int k) {
  3.         List<String> list = new LinkedList<>();
  4.         if(words==null) {
  5.             return list;
  6.         }
  7.         Map<String,Integer> map = new HashMap<>();
  8.         for (String s:words) {
  9.             if(map.get(s)==null) {
  10.                 map.put(s,1);
  11.             }else {
  12.                 int count = map.get(s);
  13.                 map.put(s,count+1);
  14.             }
  15.         }
  16.         PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
  17.             @Override
  18.             public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
  19.                 if(o1.getValue().compareTo(o2.getValue())==0) {
  20.                     return o2.getKey().compareTo(o1.getKey());
  21.                 }
  22.                 return o1.getValue()-o2.getValue();
  23.             }
  24.         });
  25.         for (Map.Entry<String,Integer> entry:map.entrySet()) {
  26.             if (queue.size() < k) {
  27.                 queue.offer(entry);
  28.             } else {
  29.                 Map.Entry<String, Integer> top = queue.peek();
  30.                 if (top != null) {
  31.                     if(top.getValue().compareTo(entry.getValue())==0) {
  32.                         if(top.getKey().compareTo(entry.getKey())>0) {
  33.                             queue.poll();
  34.                             queue.offer(entry);
  35.                         }
  36.                     }else {
  37.                         if(top.getValue()<entry.getValue()) {
  38.                             queue.poll();
  39.                             queue.offer(entry);
  40.                         }
  41.                     }
  42.                 }
  43.             }
  44.         }
  45.         for (int i = 0; i < k; i++) {
  46.             Map.Entry<String,Integer> top = queue.poll();
  47.             if(top!=null) {
  48.                 String key = top.getKey();
  49.                 list.add(key);
  50.             }
  51.         }
  52.         Collections.reverse(list);
  53.         return list;
  54.     }
  55. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/ZJRUIII/article/details/122650868

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com