題目

給一非空的單詞列表，返回前 k 個出現次數最多的單詞。

返回的答案應該按單詞出現頻率由高到低排序。如果不同的單詞有相同出現頻率，按字母順序排序。

示例 1：

輸入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
輸出: ["i", "love"]
解析: "i" 和 "love" 為出現次數最多的兩個單詞，均為2次。
注意，按字母順序 "i" 在 "love" 之前。

示例 2：

輸入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
輸出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出現次數最多的四個單詞，
出現次數依次為 4, 3, 2 和 1 次。

解題思路

1. 先使用map進行計數，統計每個單詞出現的頻率
2. 再將單詞以及其出現的頻率，放在一個二維數組中存儲
3. 對這個二維數組進行排序，按照頻率大的在前，相同頻率的話按單詞的字典序排列
4. 截取排序以后數組的前K個單詞作為結果返回

代碼

class Solution {public List<String> topKFrequent(String[] words, int k) {HashMap<String, Integer> map = new HashMap<>();for (String s : words) {map.put(s,map.getOrDefault(s,0)+1);}int n = map.size(),i=0;String[][] strings = new String[n][2];for (String string : map.keySet()) {strings[i][0]=string;strings[i][1]= String.valueOf(map.get(string));i++;}Arrays.sort(strings,(o1, o2) -> o1[1].compareTo(o2[1])==0?o1[0].compareTo(o2[0]):Integer.parseInt(o2[1])-Integer.parseInt(o1[1]));ArrayList<String> list = new ArrayList<>();for (int j = 0; j < k; j++) {list.add(strings[j][0]);}return list;}
}

結果

速度優化版代碼

取消了存儲單詞出現次數的數組，改為直接從map里面獲取出現次數

public List<String> topKFrequent(String[] words, int k) {HashMap<String, Integer> map = new HashMap<>();for (String s : words) {map.put(s,map.getOrDefault(s,0)+1);}int n = map.size(),i=0;String[] strings = new String[n];for (String string : map.keySet()) {strings[i]=string;i++;}Arrays.sort(strings,(o1, o2) -> map.get(o1)==map.get(o2)?o1.compareTo(o2):map.get(o2)-map.get(o1));ArrayList<String> list = new ArrayList<>();for (int j = 0; j < k; j++) {list.add(strings[j]);}return list;}

結果