前K個高頻的元素衍生之Map的Value與Key排序

前言

本篇文章總結來自九月份的每日一題

347-前K個高頻的元素

思考

對於系列的題目就是計算利用到Hash表的屬性的Key與Value的雙屬性，能夠滿足我們後面計算對於每一個元素出現的頻率的同時還能夠保存對於Key值的一一對應，能夠讓我們得以進行系列的計算與操作，其實對於Hash表的使用最明顯的莫過於LeetCode的第一題：兩數之和和其變形三數之和，都有利用到Hash來判斷某一個值是否存在或者對其的Value進行系列的增加或刪除操作，不需要我們進行遍歷判斷，且是線性。

思路

還是和之前一樣，我們先對數組中的值進行頻率的計算，對於不在數組其中的值對其的Value進行設置為1，對於已經存在數組其中的值對其的Value進行加一處理：

<code> 
for
(
int
 
value
: nums){
            
if
(map.containsKey(
value
)){
                map.put( 
value
,map.
get
(
value
)+
1
);
            }
            
else
{
                 map.put(
value
,
1
);
            }/<code>

在將所有的數據都存在Map中以後，剩下的就是如何將其中value值比較高的前K個取出來，也就轉換成為了如何對Map中的Value進行排序處理？排序完成之後，就可以順序取出來前K個也就是我們想要的前K高的元素。

代碼

<code>
public
 
int
 [] topKFrequent(
int
[] nums, 
int
 k) {
       
int
 []num = 
new
 
int
[k];
        Map 
map
 =  
new
 HashMap<>();
         
for
(
int
 value: nums){
            
if
(
map
.containsKey(value)){
                
map
.put(value,
map
.get(value)+
1
);
            }
            
else
{
                 
map
.put(value,
1
);
            }
           
        }
        List> 
list
 = 
new
 ArrayList<>(
map
.entrySet());
        Collections.sort(
list
, 
new
 Comparator>() {
            @Override
            
public
 
int
 compare(Map.Entry o1, Map.Entry o2) {
                
return
 o2.getValue()-o1.getValue();
            }
        });
        Map resultMap = 
new
 HashMap<>();
        
for
(Map.Entry entry: 
list
){
            resultMap.put(entry.getKey(),entry.getValue());
        }
        
for
(
int 
 i = 
0
 ;ilist.get(i).getKey();
        }
        
return
  num;
    }/<code>

對Value排序

一想到這種並非是常規的數值的排序就想到了Collections.sort但是對於其來說接收的是List類型，於是我們就定義Map類型的List。

<code>  List> 
list
 = 
new
 ArrayList<>(
map
.entrySet());/<code>

解釋：

對於Map.Entry來說就是Map中的一個接口，其是一個映射項，包含getKey和getValue方法

對於map.entrySet來說返回的而是Map中各個鍵值對映射關係的集合。

舉個例子：

<code>Iterator> it=map.entrySet().iterator();
        
while
(it.hasNext()) {
            Map.Entry entry=it.next();
            
int
 key=entry.getKey();
            
int
 
value
=entry.getValue();
            System. 
out
.println(key+
" "
+
value
);
        }/<code>

有了如上的基礎之後，因為我們的Collections.sort接收list類型的數據，所以我們在定義完成之後，就可以使用其進行對Value值的降序或者是升序的排列：

<code>Collections.sort(list, 
new
 Comparator>() {
             
            
public
 
int
 
compare
(Map.Entry o1, Map.Entry o2)
 
{
                
return
 o2.getValue()-o1.getValue(); 
                
return
 o1.getValue()-o2.getValue(); 
            }
        });/<code>

擴展

當然這裡對於Map中的數值接收的是int類型，但是有時候我們並不想對Map中的類型進行寫死，想根據，輸入的值的不同，進行不同的排序處理：

<code>   public 
static
 super V>> 
Map
 SortedMap(
Map
 map) {
     
        List< 
Map
.Entry> list = 
new
 ArrayList<>(map.entrySet());
        Collections.sort(list, 
new
 Comparator<
Map
.Entry>() {
            @Override
            public int compare(
Map
.Entry o1, 
Map
.Entry o2) {
                
return
 o1.getValue()-o2.getValue(); 
                
return
 o2.getValue()-o1.getValue(); 
            }
        });
       
        
Map
 returnMap = 
new
 LinkedHashMap();
        
for
 (
Map
.Entry entry : list) {
            returnMap.put(entry.getKey(), entry.getValue());
        }
        
return
 returnMap;
    }/<code>

測試

int類型數據

測試數據：

<code>   Map  
map
 = 
new
 HashMap<>();
       
map
.put(
"Tom"
,
2
);
       
map
.put( 
"Jack"
,
1
);
       
map
.put(
"sun"
,
4
);
       
map
.put(
"star"
,
21
);
        System.out.
println
(
"排序前--->"
 + 
map
);
        System.out.
println
(
"----------------"
);
        
map
  = SortedMap(
map
);
        System.out.
println
(
"排序後--->"
 + 
map
);/<code>

測試結果：

<code>排序前 
 
排序後/<code>

String類型數據

測試數據：

<code> Map 
map
 =  
new
 HashMap<>();
       
map
.put(
"Tom"
,
"azc"
);
       
map
.put(
"Jack"
,
"bac"
);
       
map
.put(
"sun"
,
"bzc"
);
       
map
.put(
"star"
,
"abc"
);
        System.out.
println
(
"排序前--->"
 + 
map
);
        System.out.
println
(
"----------------"
);
        
map
  = SortedMap(
map
);
        System.out.
println
(
"排序後--->"
 + 
map
);/<code>

測試結果：

<code>排序前 
 
排序後/<code>

對Key排序

在完成了對Value的排序以後來進行系列的對Key值的排序處理。對於Key值的排序就比較容易實現了。

<code>  
public
  
static
  <
K
, 
V
 extends 
Comparable
 
super
 
V
>> 
Map
<
K
, 
V
> 
SortedKey
(
Map
<
K
,
V
> 
map
){
        
K
 [] key = (
K
[]) 
map 
.keySet().toArray();
        
Arrays
.
sort
(key);
        
Map
<
K
,
V
> returnMap = new 
LinkedHashMap
<>();
        
        
for
(
K
 keys : key){
            returnMap.put(keys,
map
.
get
(keys));
        }
        
return
  returnMap;
    }/<code>

測試

String類型數據

測試數據：

<code>      Map 
map
 = 
new
 LinkedHashMap<>();
        
map
.put(
"azc"
, 
"a"
);
        
map
.put(
"abc"
, 
"b" 
);
        
map
.put(
"bzc"
, 
"d"
);
        
map
.put(
"bac"
, 
"e"
);
        System.out.
println
(
"排序前--->"
 + 
map
);
        System.out.
println
(
"----------------"
);
        
map
 = SortedKey(
map
);
        System.out.
println
(
"排序後--->"
 + 
map
);/<code>

測試結果：

<code>排序前 
 
排序後/<code>