Java Map中Value值的排序（利用Map统计次数）

L!sa3 2024-04-09 原文

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 进行降序排列。

// 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统计次数）的更多相关文章

ruby-on-rails - Rails 单表继承 : How to override the value written to the type field - 2
在我的系统中，我已经定义了STI。Dog继承自Animal，在animals表中有一个type列，其值为"Dog"。现在我想让SpecialDog继承自dog，只是为了在某些特殊情况下稍微修改一下行为。数据还是一样。我需要通过SpecialDog运行的所有查询，以返回数据库中类型为Dog的值。我的问题是因为我有一个type列，rails将WHERE"animals"."type"IN('SpecialDog')附加到我的查询中，所以我不能获取原始的Dog条目。所以我想要的是以某种方式覆盖rails在通过SpecialDog访问数据库时使用的值，使其表现得像Dog。有没有办法覆盖用于类型
ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2
我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night
ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2
我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我
ruby - 在 ruby 中使用 .try 函数和 .map 函数 - 2
我需要从json记录中获取一些值并像下面这样提取curr_json_doc['title']['genre'].map{|s|s['name']}.join(',')但对于某些记录，curr_json_doc['title']['genre']可以为空。所以我想对map和join()使用try函数。我试过如下curr_json_doc['title']['genre'].try(:map,{|s|s['name']}).try(:join,(','))但是没用。最佳答案你没有正确传递block。block被传递给参数括号外的方法
ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2
我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排
ruby-on-rails - Sunspot:如何对具有不同值的多个字段进行全文查询？ - 2
我想用sunspot重现以下原始solr查询q=exact_term_text:fooORterm_textv:foo*ORalternate_text:bar*但我无法通过标准的太阳黑子界面理解这是否可能以及如何实现，因为看起来:fulltext方法似乎不接受多个文本/搜索字段参数我不知道将什么参数作为第一个参数传递给fulltext，就好像我通过了"foo"或"bar"结果不匹配如果我传递一个空参数，我得到一个q=*:*范围过滤器(例如with(:term).starting_with('foo*')(顾名思义)作为过滤器查询应用，因此不参与评分。似乎可以手动编写字符串(或者可能使
ruby-on-rails - self 在 Rails 模型中的值(value)是什么？为什么没有明显的实例方法可用？ - 2
我的rails3.1.6应用程序中有一个自定义访问器方法，它为一个属性分配一个值，即使该值不存在。my_attr属性是一个序列化的哈希，除非为空白，否则应与给定值合并指定了值，在这种情况下，它将当前值设置为空值。(添加了检查以确保值是它们应该的值，但为简洁起见被删除，因为它们不是我的问题的一部分。)我的setter定义为:defmy_attr=(new_val)cur_val=read_attribute(:my_attr)#storecurrentvalue#makesureweareworkingwithahash,andresetvalueifablankvalueisgiven
ruby-on-rails - 在不重新查询数据库的情况下重新排序 Rails 中的事件记录？ - 2
例如，假设我有一个名为Products的模型，并且在ProductsController中，我有以下代码用于product_listView以显示已排序的产品。@products=Product.order(params[:order_by])让我们想象一下，在product_listView中，用户可以使用下拉菜单按价格、评级、重量等进行排序。数据库中的产品不会经常更改。我很难理解的是，每次用户选择新的order_by过滤器时，rails是否必须查询，或者rails是否能够以某种方式缓存事件记录以在服务器端重新排序？有没有一种方法可以编写它，以便在用户排序时rails不会重新查询结果
ruby-on-rails - 如何对对象数组进行排序？ - 2
我有一个对象如下:[{:id=>2,:fname=>"Ron",:lname=>"XXXXX",:photo=>"XXX"},{:id=>3,:fname=>"Dain",:lname=>"XXXX",:photo=>"XXXXXXX"},{:id=>1,:fname=>"Bob",:lname=>"XXXXXX",:photo=>"XXXX"}]我想按fname排序，不区分大小写，所以它会导致编号:1,3,2我该如何排序？我正在尝试:@people.sort!{|x,y|y[:fname]x[:fname]}但这没有任何效果。最佳答案
ruby - 不能将 `each` 的所有或大多数情况替换为 `map` 吗？ - 2
Enumerable#each和Enumerable#map的区别在于返回的是接收者还是映射后的结果。回到接收者是微不足道的，你通常不需要在each之后继续一个方法链，比如each{...}.another_method(我可能没见过这样的案例。即使你想回到接收者那里，你也可以通过tap来实现)。所以我认为所有或者大部分使用Enumerable#each的情况都可以用Enumerable#map代替。我错了吗？如果我是对的，each的目的是什么？map是否比each慢？编辑:我知道当您对返回值不感兴趣时使用each是一种常见的做法。我对这种做法是否存在不感兴趣，但感兴趣的是，除了从

Java Map中Value值的排序（利用Map统计次数）