背景
引起我思考Java中Map排序问题,是来源于 LeetCode 501. 二叉搜索树中的众数。
这道题要求根据一棵给定的二叉搜索树,在树中找出结点中出现次数最多的那个值,且不唯一。换句话说,也就是在树中搜索众数,且不唯一。
想法
看到这道题时,首先就想到要遍历整棵树中的每个结点,同时保存结点中值(因为最终要返回的是值)及其出现的次数。
那么保存配对数据最先想用的就是Map数据结构,Key保存结点值,Value保存值出现的次数。之后遍历树,同时保存出现的频数。实现这一点并不难,只要利用map.put函数存入key和value,同时配合map.getOrDefault函数设置value的值就可以了。代码如下:
public void traversal(TreeNode root) {
//使用了前(先)序遍历,遇到结点就保存它的值及其出现的频率
map.put(root.val, map.getOrDefault(root.val, 0) + 1);
//put(key, value): 存入key,同时存入其value
//getOrDefault(key, defaultValue): 若没有这个值,设它的值(即出现次数)为defaultValue;有这个值,则获取它的值(即出现的次数)
//由于默认值应该为1,但是考虑到有值的情况需要加1,所以默认值就设为零,统一了操作
if (root.left != null) traversal(root.left);//遍历左子树
if (root.right != null) traversal(root.right);//遍历右子树
}
目前,已经获取到树中结点值及其出现的频数。然而,问题来了,如何找出map中的众数呢?
最直接的想法就是对map排序(虽然不必要,但是偏要这么做,就是固执),那么如何对map排序呢?存在两种方法。
方法一:List + Collections.sort
查遍了一些资料中说,先创建list用于保存Map中的key-value对(Map中使用entrySet保存),之后通过Collections接口中的sort函数即可实现Map的排序。代码如下:
//创建list保存map中的key-value对,通过map.entrySet()获取map中的key-value对
List<Map.Entry<Integer,Integer>> list = new LinkedList<>(map.entrySet());
//利用Collections接口的sort函数对list进行降序排序,需要实现Comparator接口的compare方法
Collections.sort(list, new Comparator(){
public int compare(Object o1, Object o2){
//Comparable接口中的compareTo方法
//A.compareTo(B): A > B 返回正整数;A < B 返回负整数;相等,返回 0
//Comparator接口中的compare方法
//返回正整数: 升序;返回负整数: 降序
return -((Comparable)((Map.Entry)(o1)).getValue()).compareTo(((Map.Entry)(o2)).getValue());
}
});
至此,list已经排序好了,只要遍历list,然后保存进map中即可。代码如下:文章来源:https://www.toymoban.com/news/detail-430426.html
//list中保存排序好的<key, value>对,将其放入map中
map.clear();
for (Map.Entry<Integer, Integer> entry : list) {
map.put(entry.getKey(), entry.getValue());
}
方法二:PriorityQueue(推荐)
在我们已经获得 Map 后,可以通过如下方式,根据 Map 中的 Value 值来将 Key 进行降序排列。文章来源地址https://www.toymoban.com/news/detail-430426.html
// 1. 定义优先级队列(本质上是大顶堆)
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
// 2. 将 Map 中的元素放入优先级队列,会自动根据 Value 值进行降序排序。
for (Map.Entry<Integer, Integer>> entry : map.entrySet()) {
pq.offer(entry);
}
// 3. 此时,堆顶元素就是众数
int modeNumber = pq.poll().getKey();
到了这里,关于Java Map中Value值的排序(利用Map统计次数)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!