LeetCode Js-347. Top K Frequent Elements

    AllenLi
    LeetCode Js-Array

    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
};

    Related Posts