前言
本篇文章總結來自九月份的每日一題
347-前K個高頻的元素
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5iMmBjNkJjY0QTMkRzYmRjMmBDOklzYldTNzMWO4EGOk9CX0JXZ252bj91Ztl2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
思考
對于系列的題目就是計算利用到Hash表的屬性的Key與Value的雙屬性,能夠滿足我們後面計算對于每一個元素出現的頻率的同時還能夠儲存對于Key值的一一對應,能夠讓我們得以進行系列的計算與操作,其實對于Hash表的使用最明顯的莫過于LeetCode的第一題:兩數之和和其變形三數之和,都有利用到Hash來判斷某一個值是否存在或者對其的Value進行系列的增加或删除操作,不需要我們進行周遊判斷,且是線性。
思路
還是和之前一樣,我們先對數組中的值進行頻率的計算,對于不在數組其中的值對其的Value進行設定為1,對于已經存在數組其中的值對其的Value進行加一處理:
for(int value: nums){ if(map.containsKey(value)){ map.put(value,map.get(value)+1); } else{ map.put(value,1); }
在将所有的資料都存在Map中以後,剩下的就是如何将其中value值比較高的前K個取出來,也就轉換成為了如何對Map中的Value進行排序處理?排序完成之後,就可以順序取出來前K個也就是我們想要的前K高的元素。
代碼
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 ;i
對Value排序
一想到這種并非是正常的數值的排序就想到了Collections.sort但是對于其來說接收的是List類型,于是我們就定義Map類型的List。
List> list = new ArrayList<>(map.entrySet());
解釋:
對于Map.Entry來說就是Map中的一個接口,其是一個映射項,包含getKey和getValue方法
對于map.entrySet來說傳回的而是Map中各個鍵值對映射關系的集合。
舉個例子:
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); }
有了如上的基礎之後,因為我們的Collections.sort接收list類型的資料,是以我們在定義完成之後,就可以使用其進行對Value值的降序或者是升序的排列:
Collections.sort(list, new Comparator>() { @Override public int compare(Map.Entry o1, Map.Entry o2) { return o2.getValue()-o1.getValue();// 表示降序排列 return o1.getValue()-o2.getValue();// 表示升序排列 } });
擴充
當然這裡對于Map中的數值接收的是int類型,但是有時候我們并不想對Map中的類型進行寫死,想根據,輸入的值的不同,進行不同的排序處理:
public static > Map SortedMap(Map map) { List> list = new ArrayList<>(map.entrySet()); Collections.sort(list, new Comparator>() { @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; }
測試
int類型資料
測試資料:
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);
測試結果:
排序前--->{Tom=2, star=21, Jack=1, sun=4}----------------排序後--->{star=21, sun=4, Tom=2, Jack=1}
String類型資料
測試資料:
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);
測試結果:
排序前--->{Tom=azc, star=abc, Jack=bac, sun=bzc}----------------排序後--->{sun=bzc, Jack=bac, Tom=azc, star=abc}
對Key排序
在完成了對Value的排序以後來進行系列的對Key值的排序處理。對于Key值的排序就比較容易實作了。
public static > Map SortedKey(Map map){ K [] key = (K[]) map.keySet().toArray(); Arrays.sort(key); Map returnMap = new LinkedHashMap<>(); for(K keys : key){ returnMap.put(keys,map.get(keys)); } return returnMap; }
測試
String類型資料
測試資料:
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);
測試結果:
排序前--->{azc=a, abc=b, bzc=d, bac=e}----------------排序後--->{abc=b, azc=a, bac=e, bzc=d}