LeetCode Js-347. Top K Frequent Elements

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