Java Map中Value值的排序(利用Map统计次数)

这篇具有很好参考价值的文章主要介绍了Java Map中Value值的排序(利用Map统计次数)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

背景

引起我思考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中即可。代码如下:

//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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包