JAVA map排序实现

梦里梦外; 2022-01-23 09:17 254阅读 0赞

Map排序的方式有很多种，这里记录下自己总结的两种比较常用的方式：按键排序(sort by key)， 按值排序(sort by value)。

**1、按键排序**

jdk内置的java.util包下的TreeMap<K,V>既可满足此类需求，向其构造方法 TreeMap(Comparator<? super K> comparator)  传入我们自定义的比较器即可实现按键排序。

**实现代码**

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 </td> 
 <td> <code>public</code> <code>class</code> <code>MapSortDemo { </code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) { </code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Map&lt;String, String&gt; map = </code><code>new</code> <code>TreeMap&lt;String, String&gt;();</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>map.put(</code><code>"KFC"</code><code>, </code><code>"kfc"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>map.put(</code><code>"WNBA"</code><code>, </code><code>"wnba"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>map.put(</code><code>"NBA"</code><code>, </code><code>"nba"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>map.put(</code><code>"CBA"</code><code>, </code><code>"cba"</code><code>);</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Map&lt;String, String&gt; resultMap = sortMapByKey(map);&nbsp;&nbsp;&nbsp; </code><code>//按Key进行排序</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code> <code>(Map.Entry&lt;String, String&gt; entry : resultMap.entrySet()) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(entry.getKey() + </code><code>" "</code> <code>+ entry.getValue());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/**</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* 使用 Map按key进行排序</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @param map</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*/</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>Map&lt;String, String&gt; sortMapByKey(Map&lt;String, String&gt; map) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(map == </code><code>null</code> <code>|| map.isEmpty()) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>null</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Map&lt;String, String&gt; sortMap = </code><code>new</code> <code>TreeMap&lt;String, String&gt;(</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>new</code> <code>MapKeyComparator());</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sortMap.putAll(map);</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>sortMap;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

比较器类

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 </td> 
 <td> <code>class</code> <code>MapKeyComparator </code><code>implements</code> <code>Comparator&lt;String&gt;{ </code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>@Override</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>int</code> <code>compare(String str1, String str2) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>str1.compareTo(str2);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

**2、按值排序**

按值排序就相对麻烦些了，貌似没有直接可用的数据结构能处理类似需求，需要我们自己转换一下。  
Map本身按值排序是很有意义的，很多场合下都会遇到类似需求，可以认为其值是定义的某种规则或者权重。

原理：将待排序Map中的所有元素置于一个列表中，接着使用Collections的一个静态方法 sort(List<T> list, Comparator<? super T> c)  
来排序列表，同样是用比较器定义比较规则。排序后的列表中的元素再依次装入Map，为了肯定的保证Map中元素与排序后的List中的元素的顺序一致，使用了LinkedHashMap数据类型。

**实现代码**

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 </td> 
 <td> <code>public</code> <code>class</code> <code>MapSortDemo { </code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) { </code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Map&lt;String, String&gt; map = </code><code>new</code> <code>TreeMap&lt;String, String&gt;();</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>map.put(</code><code>"KFC"</code><code>, </code><code>"kfc"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>map.put(</code><code>"WNBA"</code><code>, </code><code>"wnba"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>map.put(</code><code>"NBA"</code><code>, </code><code>"nba"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>map.put(</code><code>"CBA"</code><code>, </code><code>"cba"</code><code>);</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Map&lt;String, String&gt; resultMap = sortMapByKey(map);&nbsp;&nbsp;&nbsp; </code><code>//按Key进行排序</code> <code>//&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Map&lt;String, String&gt; resultMap = sortMapByValue(map); //按Value进行排序</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code> <code>(Map.Entry&lt;String, String&gt; entry : resultMap.entrySet()) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(entry.getKey() + </code><code>" "</code> <code>+ entry.getValue());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/**</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* 使用 Map按value进行排序</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @param map</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>* @return</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>*/</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>static</code> <code>Map&lt;String, String&gt; sortMapByValue(Map&lt;String, String&gt; oriMap) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code> <code>(oriMap == </code><code>null</code> <code>|| oriMap.isEmpty()) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>null</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Map&lt;String, String&gt; sortedMap = </code><code>new</code> <code>LinkedHashMap&lt;String, String&gt;();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>List&lt;Map.Entry&lt;String, String&gt;&gt; entryList = </code><code>new</code> <code>ArrayList&lt;Map.Entry&lt;String, String&gt;&gt;(</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>oriMap.entrySet());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Collections.sort(entryList, </code><code>new</code> <code>MapValueComparator());</code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Iterator&lt;Map.Entry&lt;String, String&gt;&gt; iter = entryList.iterator();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Map.Entry&lt;String, String&gt; tmpEntry = </code><code>null</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code> <code>(iter.hasNext()) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>tmpEntry = iter.next();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>sortedMap.put(tmpEntry.getKey(), tmpEntry.getValue());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>sortedMap;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

比较器类

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 </td> 
 <td> <code>class</code> <code>MapValueComparator </code><code>implements</code> <code>Comparator&lt;Map.Entry&lt;String, String&gt;&gt; { </code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>@Override</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code> <code>int</code> <code>compare(Entry&lt;String, String&gt; me1, Entry&lt;String, String&gt; me2) { </code> &nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>me1.getValue().compareTo(me2.getValue());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

例：

在一个仓库里，有一排条形码，其中第 `i` 个条形码为 `barcodes[i]`。

请你重新排列这些条形码，使其中两个相邻的条形码 **不能** 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

class Solution {
 public int[] rearrangeBarcodes(int[] barcodes) {
 int[] res=new int[barcodes.length];
 int j=0;
 Map<Integer,Integer> map=new LinkedHashMap<>();
 for(int i=0;i<barcodes.length;i++){
 map.putIfAbsent(barcodes[i],0);
 map.put(barcodes[i],map.get(barcodes[i])+1);
 }
 ArrayList<Map.Entry<Integer,Integer>> list=new ArrayList<>(map.entrySet());
 Collections.sort(list,new c());
 Iterator itr=list.iterator();
 Map.Entry<Integer, Integer> tmpEntry = null;
 while(itr.hasNext()){
 tmpEntry=(Map.Entry<Integer,Integer>)itr.next();
 int num=tmpEntry.getValue();
 int n=tmpEntry.getKey();
 for(int i=0;i<num;i++){
 res[j]=n;
 j+=2;
 if(j>=res.length){
 j=1;
 }
 }
 }
 return res;
 }
 }
 class c implements Comparator<Map.Entry<Integer,Integer>>{
 public int compare(Map.Entry<Integer,Integer> m1,Map.Entry<Integer,Integer> m2){
 return -(m1.getValue()-m2.getValue());
 }
 }