05 August 2008
单词列表中的前k个高频单词
这道题是在「优先队列（堆）」裸题的基础上增加了字典序大小的比较。
相应的，我们不能只根据「词频大小」构建小根堆来获取前 kk 个元素，还需要结合字典序大小来做。
具体的，我们可以使用「哈希表」&「优先队列」进行求解：
1
2
3
4
5
6
7
8
9
10
使用「哈希表」来统计所有的词频
构建大小为 kk 按照「词频升序 + (词频相同)字典序倒序」的优先队列：
如果词频不相等，根据词频进行升序构建，确保堆顶元素是堆中词频最小的元素
如果词频相等，根据字典序大小进行倒序构建，结合 2.12.1 可以确保堆顶元素是堆中「词频最小 & 字典序最大」的元素
对所有元素进行遍历，尝试入堆：
堆内元素不足 kk 个：直接入堆
词频大于堆顶元素：堆顶元素不可能是前 kk 大的元素。将堆顶元素弹出，并将当前元素添加到堆中
词频小于堆顶元素；当前元素不可能是前 kk 大的元素，直接丢弃。
词频等于堆顶元素：根据当前元素与堆顶元素的字典序大小决定（如果字典序大小比堆顶元素要小则入堆）
输出堆内元素，并翻转
时间复杂度：使用哈希表统计词频，复杂度为 O(n)；使用最多 nn 个元素维护一个大小为 kk 的堆，复杂度为 O(nlogk)；输出答案复杂度为 O(k)（同时 k \leq nk≤n）。整体复杂度为O(nlogk)
空间复杂度：O(n)
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
class Solution {
public List<String> topKFrequent(String[] ws, int k) {
Map<String, Integer> map = new HashMap<>();
for (String w : ws) map.put(w, map.getOrDefault(w, 0) + 1);
PriorityQueue<Object[]> q = new PriorityQueue<>(k, (a, b)->{
// 如果词频不同，根据词频升序
int c1 = (Integer)a[0], c2 = (Integer)b[0];
if (c1 != c2) return c1 - c2;
// 如果词频相同，根据字典序倒序
String s1 = (String)a[1], s2 = (String)b[1];
return s2.compareTo(s1);
});
for (String s : map.keySet()) {
int cnt = map.get(s);
if (q.size() < k) { // 不足 k 个，直接入堆
q.add(new Object[]{cnt, s});
} else {
Object[] peek = q.peek();
if (cnt > (Integer)peek[0]) { // 词频比堆顶元素大，弹出堆顶元素，入堆
q.poll();
q.add(new Object[]{cnt, s});
} else if (cnt == (Integer)peek[0]) { // 词频与堆顶元素相同
String top = (String)peek[1];
if (s.compareTo(top) < 0) { // 且字典序大小比堆顶元素小，弹出堆顶元素，入堆
q.poll();
q.add(new Object[]{cnt, s});
}
}
}
}
List<String> ans = new ArrayList<>();
while (!q.isEmpty()) ans.add((String)q.poll()[1]);
Collections.reverse(ans);
return ans;
}
}
自定义比较器
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
class Solution {
public List<String> topKFrequent(String[] words, int k) {
List<String> list = new ArrayList<>();
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (String s : words) {
int count = map.getOrDefault(s, 0)+1;
map.put(s, count);
}
// 添加 key 值作为 list 的元素
for (String key: map.keySet()) {
list.add(key);
}
// 自定义比较器（使用优先队列也可），先比较次数，次数相等再比较字典大小
// 使得次数从大到小排列，字典从小到大排列
list.sort((s1, s2) -> {
int f = Integer.compare(map.get(s2), map.get(s1));
if (f > 0) {
return 1;
}
if (f == 0) {
return s1.compareTo(s2);
}
return -1;
});
List<String> ls = new ArrayList<String>();
// 添加前 k 多的元素
for (int i=0; i<k; i++) {
ls.add(list.get(i));
}
return ls;
}
}
TreeMap
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
class Solution {
public List<String> topKFrequent(String[] words, int k) {
// Arrays.sort(words);
Map<String, Integer> map = new TreeMap<>();
for(int i = 0;i<words.length;i++){
map.put(words[i], map.getOrDefault(words[i], 0)+1);
}
List<String> res = new ArrayList<>();
while(k!=0){
String temp = "";
int siz = 0;
for(String s:map.keySet()){
if(map.get(s)>siz){
siz = map.get(s);
temp = s;
}
}
res.add(temp);
k--;
map.remove(temp);
if(map.size()==0) break;
}
return res;
}
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*==========================================================================
Quick select first k number entry<key, frequency> with bigger frequency
then sort them.
O(n+klogk) time
O(n) space
*/
class Solution {
public List<String> topKFrequent4(String[] words, int k) {
Map<String, Integer> map = new HashMap<>();
for (String w : words) map.put(w, map.getOrDefault(w, 0) + 1);
Map.Entry<String, Integer>[] arr = new Map.Entry[map.size()];
int i = 0;
for (Map.Entry<String, Integer> e : map.entrySet()) arr[i++] = e;
quickSelect(arr, 0, arr.length - 1, k);
List<Map.Entry<String, Integer>> list = new LinkedList<>();
for (int j = 0; j < k; j++) list.add(arr[j]);
Collections.sort(list, (a, b) -> compare(a, b));
List<String> ans = new LinkedList<>();
for (Map.Entry<String, Integer> e : list) ans.add(e.getKey());
return ans;
}
private void quickSelect(Map.Entry<String, Integer>[] a, int l, int r, int k) {
while (l < r) {
int pi = partition(a, l, r);
if (pi == k - 1) break;
else if (pi < k - 1) l = pi + 1;
else r = pi - 1;
}
}
// Descending order
private int partition(Map.Entry<String, Integer>[] a, int l, int r) {
int pi = l + r >>> 1;
Map.Entry<String, Integer> pv = a[pi];
swap(a, pi, l);
int i = l + 1, n = l + 1;
while (i <= r) {
if (compare(a[i], pv) < 0) swap(a, i++, n++);
else i++;
}
n--; // note here
swap(a, n, l);
return n;
}
private void swap(Map.Entry<String, Integer>[] a, int l, int r) {
Map.Entry<String, Integer> tmp = a[l];
a[l] = a[r];
a[r] = tmp;
}
// descending order by frequency. same frequency: in lexicographical order
public static int compare(Map.Entry<String, Integer> l, Map.Entry<String, Integer> r) {
String lw = l.getKey(), rw = r.getKey();
int lf = l.getValue(), rf = r.getValue();
return (lf == rf) ? lw.compareTo(rw) : rf - lf;
}
}