数据结构：Map和Set（Java）
讲Map和Set这两个数据结构之前，我们要先了解一下搜索树的概念，因为TreeMap和TreeSet底层就是由搜索树实现的
一.搜索树
二叉搜索树也叫二叉排序树，同样也是和二叉树一样是树形结构，只不过比普通二叉树多了一些性质
性质1：若左子树不为空，那么左子树上所有的结点的值都小于根节点的值
性质2：若右子树不为空，那么右子树上所有的结点的值都大于根节点的值
性质3：它的左右子树也分别为二叉搜索树
注：里面不能有重复的元素，即值都是唯一确定的
所以什么是二叉搜索树这个问题非常简单
如图所示，就是一个二叉搜索树
确实满足上面的三条性质
接下来就对这棵树进行基本操作
1.查找
类似于二分查找，如果比该结点的值大，就往右子树找，如果比该节点的值小，就往左子树找，充分利用了二叉搜索树的性质，如果没找到就返回null或者false
模拟实现如下：
public TreeNode search(int key) {
TreeNode cur = root;
while (cur != null) {
if(cur.val < key) {
cur = cur.right;
}else if(cur.val == key) {
return cur;
}else {
cur = cur.left;
}
}
return null;
}2.插入
这时候就要分类讨论了
第一种情况：为空树时
直接让根等于该结点即可
第二种情况，不为空树时
用刚刚查找的思路，用cur找到该结点应该插入的位置，只不过要多用一个变量parent来记录插入位置的父结点，才能让parent.left=cur或者parent.right=cur
模拟实现如下：
public void insert(int key) {
//为空树时
if(root == null) {
root = new TreeNode(key);
return;
}
//不为空树时
TreeNode parent = null;
TreeNode cur = root;
TreeNode node = new TreeNode(key);
while (cur != null) {
if(cur.val < key) {
parent = cur;
cur = cur.right;
}else if(cur.val > key) {
parent = cur;
cur = cur.left;
}else {
//不能插入2个相同的数据
return;
}
}
if(parent.val > key) {
parent.left = node;
}else {
parent.right = node;
}
}3.删除（难点）
这里的情况比较多，需要认真的进行分类讨论，避免出现漏情况的问题
首先也是用查找的思路，找到要删的结点的位置（如果没有就return）
这时该结点有三种情况：
1.该结点没有左子树（cur.left==null）
2.该结点没有右子树（cur.right==null）
3.该结点既有左子树又有右子树（cur.left！=null && cur.right！=null）
我们先来讨论第一种情况
第一种情况下的第一种情况：
如果该结点是根结点，那么此时就应该直接让右孩子成为新的根结点即可
第一种情况下的第二种情况：
如果该结点不是根结点，如果cur是parent.left，那么直接让parent.left指向cur.right即可（因为cur没有左子树）
第一种情况下的第三种情况：
如果该结点不是根结点，如果cur是parent.right，那么直接让parent.right指向cur.right即可（因为cur没有左子树）
如下图
然后我们来讨论第二种情况：
与第一种情况类似，也是有三种情况
第二种情况下的第一种情况：
如果该结点是根结点，那么此时就应该直接让左孩子成为新的根结点即可
第二种情况下的第二种情况：
如果该结点不是根结点，如果cur是parent.left，那么直接让parent.left指向cur.left即可（因为cur没有右子树）
第二种情况下的第三种情况：
如果该结点不是根结点，如果cur是parent.right，那么直接让parent.right指向cur.left即可（因为cur没有右子树）
如下图
最后是第三种情况：
这种情况就比较复杂，而我们采取的方法是替换删除，即找到该子树符合删除位置的一个值将要删除的值进行覆盖，然后再将原来的那个值的位置按照前两种情况进行删除
那么如何找到符合删除位置的值呢？
根据二叉搜索树的性质可知，符合这种条件的值有两个
一个是左子树的最右结点，另一个是右子树的最左结点
为什么呢？
因为左子树的最右结点是左子树最大的值，右子树的最左结点是右子树最小的值，且左子树的最右结点的值比右子树的值都小，右子树的最左结点的值又比左子树的值都大，刚好满足覆盖条件
所以我们任意选择其中一个即可，那么怎么找到左子树的最右结点或者右子树的最左结点呢
只需要遍历查找直到该结点没有右子树或者该结点没有左子树就可以找到了
模拟实现如下：
public void remove(int key) {
TreeNode cur = root;
TreeNode parent = null;
//找到需要删除的结点的位置
while (cur != null) {
if(cur.val < key) {
parent = cur;
cur = cur.right;
}else if(cur.val > key) {
parent = cur;
cur = cur.left;
}else {
//找到删除位置了，进行删除
removeNode(parent,cur);
return;
}
}
}
private void removeNode(TreeNode parent, TreeNode cur) {
//第一种情况
if(cur.left == null) {
if(cur == root) {
root = cur.right;
}else if(parent.left == cur) {
parent.left = cur.right;
}else {
parent.right = cur.right;
}
}else if(cur.right == null) {//第二种情况
if(cur == root) {
root = cur.left;
}else if(parent.left == cur) {
parent.left = cur.left;
}else {
parent.right = cur.left;
}
}else {//第三种情况
TreeNode targetParent = cur;
//这里用的是右子树的最左结点作为覆盖结点
TreeNode target = cur.right;
while (target.left != null) {
targetParent = target;
target = target.left;
}
//进行覆盖
cur.val = target.val;
//对原来的右子树的最左结点进行删除
if(targetParent.left == target) {
targetParent.left = target.right;
}else {
targetParent.right = target.right;
}
}
}
}性能分析
因为插入和删除都用到了查找，所以查找的效率代表了二叉搜索树中各个操作的性能
而其中分为最优情况和最坏情况
如下图所示
所以根据二叉树不同的类型，决定了二叉搜索树的性能，如果是完全二叉树，那么每次就能排除一半，如果是单支树，那么每次只能排除一个
而时间复杂度是以最坏情况来决定的，所以在最差情况下的最差情况，即为单支树，且要查找的结点又刚好在最后一个，那么时间复杂度为O（N）
回到Map和Set
Java类集如下
Map和Set都用于搜索相关的场景，其中主要使用的分支有TreeSet，HashSet，TreeMap，HashMap，而TreeSet和TreeMap就是由搜索树实现的，准确来说是红黑树（是一颗近似平衡的二叉搜索树，即在二叉搜索树的基础上加上了颜色以及红黑树性质验证，属于高阶数据结构，以后我们会学习）
二.Map
1.Map和Set的区别
首先先讲一下Map和Set的区别，搜索一般有两种模型
第一种是纯Key模型，即就查那一个关键字，比如在字典里面查找某个单词是否存在
第二种是Key—Value模型，即该关键字对应的某个值，比如统计该字典中某个单词出现的次数，此时Key就是某个单词，Value就是出现的次数（如果学过python，就是python的字典，键值对的意思，很好理解）
而Set对应的就是纯Key模型，Map对应的就是Key—Value模型
2.Map的说明
Map是一个接口，不能进行实例化，只能通过TreeMap或者HashMap进行实例化，其中Key不能重复，而value可以重复
关于Map的一些常用方法如下：
大致分类的话
输入：put
输出：get，getOrDefault
如果不确定是否有某个key，怕返回null的话就可以使用getOrDefault（注：这里有个小细节，如果用get的话，key不存在，如果使用接收返回值的变量为包装类：比如Integer等，那么此时不会报异常，会接收null，但是如果使用接收返回值的变量为基本数据类型：比如int等，那么此时就会报异常，因为在这个过程中会进行自动拆箱操作，而null是不能进行自动拆箱操作的，这时就会报空指针异常）
删除：remove
返回集合：keySet，values，entrySet
这三个方法就是Map转Set的方法，为什么要将Map转Set呢，因为Map没有方法遍历，只有Set有，后面讲到Set会将遍历方式
除此之外，还有一个Map.Entry<K,V>这个类型，这个其实是Map内部实现的用来存放<key,value>键值对映射关系的内部类，该内部类提供了<key,value>的获取，value的设置
刚刚的Map的方法里面也确实没有getKey的方法，只能得到value的值，所以就可以通过这个内部类来得到key
或许你还有个疑问，为什么keySet的返回类型是Set，values的返回类型是Collection（Collection是Set的一个父类，Set只是继承自Collection的一个接口类），因为Set是去重的集合，即Set里面每个元素都是唯一的，即使传入两个一样值的也只会存放一个值，而Collection是可重复的集合，传入两个一样值的也会存放两个值。而Map里面要求的Key是唯一的，value是不唯一的，所以就用对应不同返回值的集合
判断：containsKey，containsValue
注：
TreeMap插入键值对的时候，key不能为空，否则就抛出空指针异常，但是value可以为空，而HashMap的key和value都可以为空
Map里面的键值对的key不能直接修改，value可以修改（即通过put相同的key，value就会进行覆盖），而如果要修改key，那么只能先将key删除（remove），然后再重新插入（put）
TreeMap和HashMap的区别（后面我们会着重讲HashMap，因为它的时间复杂度太厉害了，直接到了O（1））
三.Set
1.Set的说明
Set里面只存一个Key，并且要求Key一定要唯一
Set的常用方法如下：
大致分类：
输入：add，addAll
其中add是添加的一个元素，addAll是添加的一个集合
输出：toArray
删除：clear，remove
其中clear是全删，remove是单删
判断：contains，containsAll，isEmpty
其中contains判断的是一个元素，而containsAll判断的是一个集合
个数：size
遍历：iterator
这里就可以通过迭代器来进行遍历，这是其中一个遍历方式，除此之外还要foreach遍历的方式（即我们刚刚讲的entryset）
遍历代码（迭代器）：
TreeSet<String> set=new TreeSet<>();
Iterator<String> it= set.iterator();
while (it.hasNext()){
System.out.print(it.next()+" ");
}
System.out.println();遍历代码（foreach）：
HashMap<String,Integer> map=new HashMap<>();
map.put("hello", 11);
map.put("hello2", 12);
Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
for (Map.Entry<String,Integer> entry:entrySet){
System.out.println("key: "+entry.getKey()+"val: "+entry.getValue());
}这样就可以遍历map了
注：
1.Set是继承自Collection的一个接口类
3.TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
4.Set最大的功能就是对集合中的元素进行去重
5.实现Set接口的常用类有TreeSet和Hashset，还有一个LinkedHashset，LinkedHashset是在Hashset的基础上维护了一个双向链表来记录元素的插入次序。
6.Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
7.TreeSet中不能插入null的key，HashSet可以
TreeSet和HashSet的区别
四.哈希表
1.概念
首先我们要知道为什么需要哈希表这种数据结构，以及它为什么这么重要
之前我们所学过的所有数据结构，如果要进行查找元素的操作时，一般都是通过多次比较，进行排除，最后查找到那个目标元素，而一系列的优化算法，也只是让比较次数变得更少，一次性排除的元素更多，使得查询效率更高
难道我们就不能一下子就找到那个元素吗
诶，其实我们之前学过一个数据结构，它就能一次性查找到目标元素——数组
我们可以用数组的下标一下子就找到对应的元素，当然我们得提前知道目标元素对应的下标是多少，所以之前我们大部分时间都花在如何找到该下标的问题上
而数组里面其实就有一个很重要的特性，那就是一一映射，即一个下标映射对应下标的值，这样子查找的时间复杂度就来到了O（1）
而哈希表就是重要发挥了这个特性
其实哈希表就是数组加上一个哈希函数构成，每次传入的值根据哈希函数运算后得到值就放到对应的位置
如下图：
我们这里就假设哈希函数为key%capacity，这时就能根据该函数进行数据分类
2.哈希冲突
当然这里就会出现一个问题，如果出现4和14的话，那么根据哈希函数的运算后都为4，那么它们就都放在同一个哈希地址，这种情况就叫做哈希冲突或者哈希碰撞
其实我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这也就是说，发生冲突是必然的，我们能做的只是尽量降低冲突率
1.避免
其中一个原因就是哈希函数设计不合理，哈希函数应该满足：定义域必须包括需要存储的全部的关键字，如果有m个哈希地址，那么值域必须为0—m-1；哈希函数计算出来的地址必须能均匀分布在整个空间中，且哈希函数应该比较简单
常见的哈希函数如下：
其中直接定制法和除留余数法是比较常用的，其他都根据不同情况使用其他不同的方法
但是都只能降低哈希冲突的可能性，无法避免哈希冲突
还有另外一种原因，那就是对负载因子a进行调节
什么是负载因子呢，其实负载因子a就等于：填入表中的元素个数/散列表的长度
也就是占比的问题，肯定就是让占比越小越好
冲突率和负载因子的函数关系如下：
我们大致控制负载因子在0.7—0.8以下，一旦超过0.8，那么冲突率就会按照指数曲线上升，而我们的Java的系统就限制负载因子为0.75，超过了的话就扩容
而我们要放入的元素个数肯定是不能随意减少的，所以只能让数组变大，这也是为什么哈希的时间复杂度为什么小的原因，就是采用了用空间换时间的策略
2.解决
如果避免后仍然出现冲突，那么只能进行解决了
两种常见解决哈希冲突的方法：闭散列和开散列
闭散列：也叫做开放地址法，就是当发生哈希冲突时，如果哈希表未被装满，那么就说明哈希表必然还有空位置，这时只需要将key存放到发生冲突位置的“下一个”空位置去即可
那么这时候的问题就是怎么找到“下一个”空位置
也有两种探测方法：线性探测和二次探测
线性探测就是往后一个一个找，直到找到下一个空位置为止
还是以这个为例，如果出现14，那么此时根据哈希函数应该在下标4这里，但是因为已经有元素了，所以发生了哈希冲突，这时候根据线性探测，就会往后探测，找到下标为8这个空位置，那么14就放在8这个下标的位置了
但是线性探测也有缺点，那就是将产生冲突的数据全部堆积在一起，这就会影响其找下一个空位置，使得往后探测多次，仍然没找到空位置，这时候就可以采用二次探测
二次探测找下一个空位置的方法为：Hi=(H0+i^2)%m,或者:Hi=(H0-i^2)% m。其中i= 1,2,3……， H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
由闭散列可知，最大缺陷就是空间利用率不高，经常需要扩容然后空一部分地址不用，这也是哈希的缺陷
而另一种方法开散列也叫做哈希桶，这个是需要重点掌握的
开散列法也叫做链地址法，对的，就是用到了链表
哈希桶结构直观图如下：
而这里如果是值的话，还可以直接比较，但如果是类，那么就需要重写equals和hashcode方法
这里有一个新的方法：hashcode，这个方法是Java帮我们实现好的，即它可以将任意一个类通过一个哈希码公式，最后会得到一个哈希码，而每一个的哈希码都不一样，这样就能通过比较哈希码来判断两个类是否是同一个类了
你可能会有疑惑，我就不能在equals里面直接就定义要比较的变量吗，为什么一定要用哈希码来进行比较呢，比如有一个类Person，里面有name，age变量，我们不能在equals里用name来比较是否一样吗，这时你可能会反应过来，重名的人，这时如果说那就再对age进行比较，那么就还有可能出现同龄且同名的人，比如中国有多少个张伟，所以这样比较下去是比较不完的，除非使用身份证号来进行比较，那么其实哈希码就相当于身份证号的作用，每一个类只对应一个哈希码，和身份证号码都具有唯一性
理论大致都讲完了，接下来就进行5道题目进行练习吧
五.OJ练习
1.
思路：
这道题之前在学位运算符的时候做过，那时候就直接采用异或的方法直接找到只出现一次的元素
代码1（异或）：
class Solution {
public int singleNumber(int[] nums) {
int ret=nums[0];
for(int i=1;i<nums.length;i++){
ret^=nums[i];
}
return ret;
}
}当然异或的方法可以说是这道题的最优解，但我们现在主要练习Set和Map，所以还可以采用这次学到的知识来解决这道题
代码2（map转set）：
class Solution {
public int singleNumber(int[] nums) {
//先存储值和出现次数的一一映射关系
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
if(!map.containsKey(nums[i])){
map.put(nums[i],1);
}else{
int val=map.get(nums[i]);
map.put(nums[i],val+1);
}
}
//通过entryset来遍历，找到出现次数为1的值
Set<Map.Entry<Integer,Integer>> entryset=map.entrySet();
for(Map.Entry<Integer,Integer> entry:entryset){
if(entry.getValue()==1){
return entry.getKey();
}
}
//没找到（题目说了一定会有，但必须要照顾编译器，不然不通过）
return -1;
}
}代码3（set）：
class Solution {
public int singleNumber(int[] nums) {
//通过set来存储只出现一次的值
HashSet<Integer> set=new HashSet<>();
for(int i=0;i<nums.length;i++){
//出现第二次就删除
if(set.contains(nums[i])){
set.remove(nums[i]);
}else{//出现第一次就添加
set.add(nums[i]);
}
}
//遍历数组找到只出现一次的值
for(int i=0;i<nums.length;i++){
if(set.contains(nums[i])){
return nums[i];
}
}
//没找到，照顾编译器
return -1;
}
}2.
思路：
这道题主要难在复制的结点地址不知道，比如复制当前结点后，其next和random指向的结点都还没有创建出来，根本无法进行赋值
所以这道题要先把所有结点都创建出来，但是如果没有next和random来指向它们，它们创建后就无法被找到了，所以要通过map的映射关系来记录创建的结点，而映射关系就为老节点对应新结点
这样就可以通过老节点来对新结点进行next和random的复制
代码：
class Solution {
public Node copyRandomList(Node head) {
//先复制结点val，但并不复制next和random，并将新老结点映射关系存进map
HashMap<Node,Node> map=new HashMap<>();
Node cur=head;
while(cur!=null){
map.put(cur,new Node(cur.val));
cur=cur.next;
}
cur=head;
//通过映射关系完善next和random
while(cur!=null){
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
}注：null的结点没必要put（null，null），因为map里面默认就有(null，null)这对映射关系
3.
思路：
第一反应的话是暴力枚举，通过两层for循环，第一层遍历stones，第二层遍历jewels，如果当前的石头在jewels中找到的话，计数器count就++
代码（暴力）：
class Solution {
public int numJewelsInStones(String jewels, String stones) {
//定义一个计数器
int count=0;
//第一层循环遍历石头
for(int i=0;i<stones.length();i++){
//拿出当前的石头
char ch=stones.charAt(i);
//去遍历宝石
for(int j=0;j<jewels.length();j++){
//如果这块石头是宝石，计数器就++
if(ch==jewels.charAt(j)){
count++;
break;
}
}
}
//返回计数器
return count;
}
}然后也可以用set来保存宝石的类型，然后再遍历石头，看看这块石头是否在set里面，如果在，计数器就++
代码：
class Solution {
public int numJewelsInStones(String jewels, String stones) {
//计数器和set
int count=0;
HashSet<Character> set=new HashSet<>();
//将宝石类型全部放进set
for(int i=0;i<jewels.length();i++){
set.add(jewels.charAt(i));
}
//遍历石头
for(int i=0;i<stones.length();i++){
char ch=stones.charAt(i);
//如果该石头是宝石
if(set.contains(ch)){
count++;
}
}
//返回计数器
return count;
}
}虽然看样子好像都差不多，但暴力的时间复杂度为O（N^2），而用set的话时间复杂度为O（2N），也就是O（N），效率要更高一点
4.
思路：
题意很简单，就是找哪些键是坏的，然后输出这些坏的键且用大写输出
方法1：
利用Set去重，将第一行字符串放进去，并且在放进去的时候，进行小写转大写的操作，操作完后，再遍历第二行字符串，如果set里面有该字符，就说明该键是好的，那么此时就将该字符从set里面删掉，当然这里操作之前先将字符进行小写转大写的操作。那么最后set剩下的就全都是坏掉的键了
这里有一个注意的点，如果使用HashSet就会不通过，原因就是顺序上有问题，根据题目示例来看，是按照先后顺序来输出坏的键，也就是说我们遍历第一行字符串的时候，必须按照尾插的方式来进行插入，但是HashSet会根据哈希值等规则散列来进行插入，也就是没有所谓的尾插和头插，比较“随机”“跳跃”的插入，所以最后这道题会输出T7I，而解决办法就是使用LinkedHashSet，LinkedHashSet继承了HashSet，并添加了一个双向链表来记录元素插入的顺序，而此时的add就会按照尾插的顺序进行插入（很可惜，Java中没有实现头插的方法）
代码1：
import java.util.Scanner;
import java.util.LinkedHashSet;
import java.util.Iterator;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s=in.nextLine();
String s1=in.nextLine();
//将第一行字符串添加到Set里面
LinkedHashSet<Character> set=new LinkedHashSet<>();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
//进行小写转大写
if(ch>='a' && ch<='z'){
ch-=32;
}
set.add(ch);
}
//对第二个字符串进行遍历
for(int i=0;i<s1.length();i++){
char ch=s1.charAt(i);
//进行小写转大写
if(ch>='a' && ch<='z'){
ch-=32;
}
//如果有，则说明这个键是好的，删除
if(set.contains(ch)){
set.remove(ch);
}
}
//剩下的就都是坏的，进行遍历输出
Iterator<Character> it=set.iterator();
while(it.hasNext()){
System.out.print(it.next());
}
return;
}
}方法二：
这回就采用创建两个Set，，第一个Set用来保存第二个字符串，第二个Set遍历第一个字符串，通过进行判断，将坏的键放进去并且打印，这样是找到一个就打印一个，就不需要考虑顺序问题了
代码2：
import java.util.Scanner;
import java.util.HashSet;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s=in.nextLine();
String s1=in.nextLine();
//小写转大写
s=s.toUpperCase();
s1=s1.toUpperCase();
//将第二行字符串添加到Set1里面
HashSet<Character> set1=new HashSet<>();
for(int i=0;i<s1.length();i++){
char ch=s1.charAt(i);
set1.add(ch);
}
//对第一个字符串进行遍历
HashSet<Character> set2=new HashSet<>();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
//如果第一个字符串里没有并且还是第一次出现，就说明坏了，打印
if(!set1.contains(ch)&&!set2.contains(ch)){
set2.add(ch);
System.out.print(ch);
}
}
return;
}
}5.
思路：
这道题大致有两个步骤，第一个步骤是统计每个单词出现的次数，第二个步骤是将这些单词按照次数从高到低顺序返回前K个
第一个步骤很简单，就是用哈希表将单词与次数建立起一一映射关系，就不多说了
第二个步骤要稍微绕一点，因为出现了前K个问题，也就是TOPK问题，那么第一反应就是想到堆的知识，利用优先级队列这个数据结构建立对应的小根堆和大根堆，根据这道题的要求是将次数前K多的单词进行返回，那么也就是要建立小根堆
建立完小根堆后，就要重写比较规则了，根据题目要求可知，有两种比较方法，第一种是频率不一样的时候，按照频率大小进行比较，第二种是频率一样的时候，按照字典顺序进行比较，这里又有一点比较绕，那就是根据示例1输出可知，字典序排在前面的优先级更高，那么放进小根堆的时候，则是要让字典序排在前面的优先级更低，这样优先淘汰出去的元素才是字典序排在后面的，所以第二种这里比较的时候，又要用大根堆的比较方法来进行比较
class Solution {
public List<String> topKFrequent(String[] words, int k) {
//1.先将每个单词出现的次数存进map
HashMap<String,Integer> map=new HashMap<>();
for(String word:words){
if(!map.containsKey(word)){
map.put(word,1);
}else{
int val=map.get(word);
map.put(word,val+1);
}
}
//2.因为要找前k个出现次数最多的，所以要建小根堆
PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map. Entry<String,Integer>>(){//这里利用了匿名内部类的方式进行传参
public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
//如果次数相同，那就将字典顺序靠后的放在上面,采用大根堆的比较方法
if(o1.getValue().compareTo(o2.getValue())==0){
return o2.getKey().compareTo(o1.getKey());
}else{
return o1.getValue().compareTo(o2.getValue());
}
}
});
for(Map.Entry<String,Integer> entry:map.entrySet()){
//先放进去前K个
if(minHeap.size()<k){
minHeap.offer(entry);
}else{//放完K个后，进行比较
Map.Entry<String,Integer> top=minHeap.peek();
//如果top的次数比该单词少，top出去，该单词进来
if(top.getValue().compareTo(entry.getValue())<0){
minHeap.poll();
minHeap.offer(entry);
}else if(top.getValue().compareTo(entry.getValue())==0){//次数一样，如果top字典序比该单词更后
if(top.getKey().compareTo(entry.getKey())>0){
minHeap.poll();
minHeap.offer(entry);
}
}
}
}
//将堆元素出堆
ArrayList<String> list=new ArrayList<>();
for(int i=0;i<k;i++){
Map.Entry<String,Integer> tmp=minHeap.poll();
list.add(tmp.getKey());
}
//因为是小根堆，所以次数小的在前面了，要进行翻转
Collections.reverse(list);
return list;
}
}这道题会比较难，一是逻辑会有点绕，二是很考验代码基本功，不仅牵扯了哈希表，还有TOPK问题的堆（优先级队列），以及比较器的相关知识，还用到了顺序表和collections类的方法，很能通过这道题检查出自己代码的基础能力
以上就是关于Map和Set的大致比较全面知识了，是所有数据结构中最重要的数据结构，没有之一，一定要达到熟练掌握的程度，接下来还会学习更多数据结构，一起加油！
原文地址：https://blog.csdn.net/2301_80369371/article/details/143866574
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！