今日學習的文章鏈接和視頻鏈接
leetcode題目地址：347.前 K 個高頻元素
?代碼隨想錄題解地址：代碼隨想錄
題目簡介
給你一個整數數組?nums?和一個整數?k?，請你返回其中出現頻率前?k?高的元素。你可以按?任意順序?返回答案。
看到題目的第一想法(可以貼代碼）
1. 想不到怎么使用stack和queue來解決該問題，采用的是直線思維。
先對數組排序，再遍歷數組，用hashmap才存儲元素值（key）和元素出現的次數（value），然后對hashmap的valueSet進行降序排序，再取前k個元素，作為result。
class Solution {public int[] topKFrequent(int[] nums, int k) {//只有一個元素的情況if(nums.length == 1) return nums;//存儲最終結果int[] res = new int[k];//先對原始數組進行排序Arrays.sort(nums);//存儲數字和他們出現的頻率HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();int temp = nums[0];int count = 1;for(int i = 1; i < nums.length; i++){//如果和上一個數一致，則該數出現次數+1if(nums[i] == temp){count++;}else{//如果和上一個數不同，則識別為另一個數字的開頭hm.put(temp,count);temp = nums[i];count = 1;}//判定是否到末尾，需要回收末尾（末尾只剩一個數 or 末尾連續幾個數都一樣 時，都只需要put就行）if(i == nums.length - 1){hm.put(temp,count);}}List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(hm.entrySet());// 使用Collections.sort()排序，按value，即按出現次數進行排序Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {@Overridepublic int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {return o2.getValue().compareTo(o1.getValue());}});// for-each循環, 獲得排序后的結果int index = 0;for (Map.Entry<Integer, Integer> mapping : list){//System.out.println(mapping.getKey() + ":" + mapping.getValue());//判定是否已獲取k個最高頻數字if(index != k){res[index++] = mapping.getKey();}else{break;}}return res;}
}實現過程中遇到哪些困難
1.?想不到怎么使用stack和queue來解決該問題
看完代碼隨想錄之后的想法
【解題思路】和我的基本一致，但在對“元素出現頻率”進行排序時，我用的是普通排序時間復雜度為n*log(n)，答案采用小頂堆排序，時間復雜度為n*log(k)
【想法】無
標準答案
class Solution {//解法2：基于小頂堆實現public int[] topKFrequent2(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();//key為數組元素值,val為對應出現次數for(int num:nums){map.put(num,map.getOrDefault(num,0)+1);}//在優先隊列中存儲二元組(num,cnt),cnt表示元素值num在數組中的出現次數//出現次數按從隊頭到隊尾的順序是從小到大排,出現次數最低的在隊頭(相當于小頂堆)PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);for(Map.Entry<Integer,Integer> entry:map.entrySet()){//小頂堆只需要維持k個元素有序if(pq.size()<k){//小頂堆元素個數小于k個時直接加pq.add(new int[]{entry.getKey(),entry.getValue()});}else{if(entry.getValue()>pq.peek()[1]){//當前元素出現次數大于小頂堆的根結點(這k個元素中出現次數最少的那個)pq.poll();//彈出隊頭(小頂堆的根結點),即把堆里出現次數最少的那個刪除,留下的就是出現次數多的了pq.add(new int[]{entry.getKey(),entry.getValue()});}}}int[] ans = new int[k];for(int i=k-1;i>=0;i--){//依次彈出小頂堆,先彈出的是堆的根,出現次數少,后面彈出的出現次數多ans[i] = pq.poll()[0];}return ans;}
}學習時長
略
今日收獲
1. 使用Collections.sort()排序，按value排序
List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(hm.entrySet());// 使用Collections.sort()排序，按value排序
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {@Overridepublic int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {return o2.getValue().compareTo(o1.getValue());}
});// for-each循環
int index = 0;
for (Map.Entry<Integer, Integer> mapping : list){System.out.println(mapping.getKey() + ":" + mapping.getValue());if(index != k){res[index++] = mapping.getKey();}else{break;}
}2. PriorityQueue小頂堆
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //小頂堆，默認容量為11
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>(){ //大頂堆，容量11@Overridepublic int compare(Integer i1,Integer i2){return i2-i1;}
});
ps: add自動維持頂部為最小的值。?
3. HashMap獲取key序列或value序列
HashMap<String, Integer> map = new HashMap<String, Integer>();map.put("Kobe", 1);map.put("Jordan", 2);map.put("James", 3);//通過keySet()獲取key，再通過map.get(key)獲取valueSet<String> set = map.keySet();for(String str : set) {System.out.println(str + " " + map.get(str));}System.out.println( "------------" );//通過map.entrySet()獲得鍵值對，性能較高Set<Entry<String, Integer>> en = map.entrySet();for(Entry<String, Integer> entry : en) {System.out.println(entry.getKey() + " " + entry.getValue());}System.out.println( "------------" );//通過values()取值Collection<Integer> values = map.values();for(Integer i : values)System.out.println(i); //上面似乎有bug
//-------------------------------------------------------------// 1. 使用 Iterator 遍歷 EntrySetIterator < Entry < Integer, String >> iterator = coursesMap.entrySet().iterator();while (iterator.hasNext()) {Entry < Integer, String > entry = iterator.next();System.out.println(entry.getKey());System.out.println(entry.getValue());}// 2. 使用 Iterator 遍歷 HashMap KeySetIterator < Integer > iterator = coursesMap.keySet().iterator();while (iterator.hasNext()) {Integer key = iterator.next();System.out.println(key);System.out.println(coursesMap.get(key));}// 3. 使用 For-each 循環遍歷 HashMapfor (Map.Entry < Integer, String > entry: coursesMap.entrySet()) {System.out.println(entry.getKey());System.out.println(entry.getValue());}// 4. 使用 Lambda 表達式遍歷 HashMapcoursesMap.forEach((key, value) -> {System.out.println(key);System.out.println(value);});
