jotting

ⓁⒸ ‧‧‧ 347. Top K Frequent Elements

Posted on | Post modified | In
前 K 個頻繁出現的元素

347. Top K Frequent Elements 前 K 個頻繁出現的元素

❀ Origin

Problem

Given a non-empty array of integers, return the k most frequent elements.

Example

1
2
Input:  nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Note

  • You may assume _k_ is always valid, 1 ≤ _k_ ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

❀ 翻譯

問題

給定一個非空的整數陣列, 回傳 k 個最頻繁出現的元素.

注意

  • 你可以假設 _k_ 始終有效, 1 ≤ _k_ ≤ 獨一無二的元素的數量
  • 你算法的時間複雜度必須優於 O(n log n), 其中 n 是陣列的大小.

❀ Solution

JavaScript

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
65
66
67
68
69
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
	/**
	 * 用 obj 或 Map() 的方式來計算每個元素出現了幾次
	 * 將陣列元素的值當作物件 obj 的 key ( obj[value] )
	 * obj 的 value 則為次數
	 */
	const freqs = nums.reduce((obj, value) => {
		obj[value] = obj[value] + 1 || 1;
		return obj;
	}, {});

	/**
	 * 用 freqs 新建一個 Object.keys()
	 * 並搭配 freqs 做排序
	 * 之後以 slice() 取到目標數量 k
	 * 再用 map() 整理新的陣列,
	 * 因為Object.keys()的關係, 故用 Number(key) 傳入 key
	 */
	return Object.keys(freqs)
		.sort((a, b) => freqs[b] - freqs[a])
		.slice(0, k)
		.map(key => Number(key));
};

let nums = [1, 1, 1, 2, 2, 3];
let k = 2;
console.log(topKFrequent(nums, k));

/**
 * 別種方式
 */
// var topKFrequent = function(nums, k) {
// 	var hash = {},
// 		res = [];
// 	nums.forEach(function(value) {
// 		hash[value] = hash[value] + 1 || 1;
// 	});
// 	Object.keys(hash)
// 		.sort(function(a, b) {
// 			return hash[b] - hash[a];
// 		})
// 		.slice(0, k)
// 		.forEach(function(x) {
// 			res.push(parseInt(x));
// 		});
// 	return res;
// };

// var topKFrequent = function(nums, k) {
//     const freqs = nums.reduce((map, value) => {
//         if(map.has(value)) {
//             map.set(value, map.get(value) + 1)
//         } else {
//             map.set(value, 1)
//         }
//         return map;
//     }, new Map());

//     return Array
//         .from(freqs.entries())
//         .sort((entry1, entry2) => entry2[1] - entry1[1])
//         .slice(0,k)
//         .map(entry => entry[0])
// };