LeetCode(top100)前k個高頻元素

前k個高頻元素

題目描述

給定一個非空的整數陣列，返回其中出現頻率前 k 高的元素。

題目分析

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
輸入: nums = [1], k = 1
輸出: [1]
提示：

你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 陣列中不相同的元素的個數。
你的演算法的時間複雜度必須優於 O(n log n) , n 是陣列的大小。
題目數據保證答案唯一，換句話說，陣列中前 k 個高頻元素的集合是唯一的。
你可以按任意順序返回答案。

思路（一）

map和陣列排序方法

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    //[...new Set(array)] 一種陣列去重方法
    let arr = [...new Set(nums)]     //nums=[1,1,1,2,2,3] arr=[1,2,3]
   //統計陣列中每個元素出現的次數
    var map=new Map();
    for(let c of nums){
        if(map.has(c)){
            map.set(c,map.get(c)+1)
        }else{
            map.set(c,1);
        }
    }
    
     //根據陣列中每個元素出現的次數大小對陣列中的元素進行排序，取前k大
     return arr.sort((a, b) => map.get(b) - map.get(a)).slice(0, k);
};

思路（二）

桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分佈，將數據分到有限數量的桶裏，每個桶再分別排序（有可能再使用別的排序演算法或是以遞回方式繼續使用桶排序進行排）。

首先使用 map 來儲存頻率
然後建立一個數組（有數量的桶），將頻率作爲陣列下標，對於出現頻率不同的數位集合，存入對應的陣列下標（桶內）即可

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
   let map=new Map();     //使用map統計元素key和頻率value
   for(let c of nums){
       if(map.has(c)){
           map.set(c,map.get(c)+1);
       }else{
           map.set(c,1);
       }
   }
    if(map.size <= k) {    //如果統計後的map小於k，直接將map中所有的元素返回
         return [...map.keys()]
     }
    return bucketSort(map,k);
   
};
    let bucketSort = (map, k) => {
         let arr = [], res = []
         map.forEach((value, key) => {
          // 利用對映關係（出現頻率作爲下標）將數據分配到各個桶中
            if(!arr[value]) {     //以map中的頻率value爲下標，將元素key，對應對映到arr陣列中（相當於按頻率大小將元素從小到大排序）
               arr[value] = [key]
             } else {
                 arr[value].push(key)
        }
    })

    for(let i=0;i<arr.length;i++){
        if(arr[i]){
            res.push(...arr[i]); //注意將arr[i]前面填上...arr[i]
        }        
    }
    return res.slice(res.length-k);

    }