Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
給予一個整數陣列 nums 和一個整數 k,回傳 k 個最頻繁的元素。你可以回傳任何順序的答案。
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Solution:
1. 宣告 object 為物件。
2. 依序將 nums 中的元素取出:
如果第一次取,則放入 object 物件並給予數值 0 + 1。
反之,如果已經存在 object,則數值+1。
3. 宣告 object 物件中的屬性字串,並以陣列的方式回傳。
console.log(object) --> { '1': 3, '2': 2, '3': 1 } let arr = Object.keys(object); console.log(arr) --> [ '1', '2', '3' ]
4. 使用 sort 排序搭配箭頭函式,將物件進行降冪排序。
5. 使用 slice 回傳 k 的陣列元素。
Code 1:
var topKFrequent = function (nums, k) { let object = {} for (let num of nums) object[num] = (object[num] || 0) + 1 return Object.keys(object).sort((a, b) => object[b] - object[a]).slice(0, k) };
FlowChart:
Example 1
Input: nums = [1,1,1,2,2,3], k = 2 object = { '1': 3, '2': 2, '3': 1 } return Object.keys(object).sort((a, b) => object[b] - object[a]).slice(0, 2) //[ '1', '2' ]
Example 2
Input: nums = [1], k = 1 object = { '1': 1 } return Object.keys(object).sort((a, b) => object[b] - object[a]).slice(0, 1) //[ '1' ]
Object.keys():
var obj = { 0: 'a', 1: 'b', 2: 'c' }; console.log(Object.keys(obj)); // console: ['0', '1', '2']
Array.prototype.sort():array.sort((a, b) => a – b)
var numbers = [4, 2, 5, 1, 3]; numbers.sort(function(a, b) { return a - b; }); console.log(numbers); // [1, 2, 3, 4, 5]
Code 2: map
var topKFrequent = function(nums, k) { let map = new Map() for (const num of nums) { map.set(num, (map.get(num) || 0) + 1) } return Array.from(map).sort((a, b) => b[1] - a[1]).slice(0, k).map(([num]) => num) };
Code 3: bucket sort
var topKFrequent = function(nums, k) { const hashtable = {}; const bucket = []; const result = []; for (let num of nums) { hashtable[num] = hashtable[num] ? ++hashtable[num] : 1 } for (let [num, freq] of Object.entries(hashtable)) { bucket[freq] = bucket[freq] ? [...bucket[freq], num] : [num] } for (let i = bucket.length - 1; i >= 0; i--) { if (bucket[i]) result.push(...bucket[i]) if (result.length === k) break } return result };