給定一個(gè)非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。

示例 1:

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

示例 2:

輸入: nums = [1], k = 1 
輸出: [1] 

提示：

• 你可以假設(shè)給定的 k 總是合理的，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個(gè)數(shù)。
• 你的算法的時(shí)間復(fù)雜度必須優(yōu)于 O(nlogn) , n 是數(shù)組的大小。
• 題目數(shù)據(jù)保證答案唯一，換句話說，數(shù)組中前 k 個(gè)高頻元素的集合是唯一的。
• 你可以按任意順序返回答案。

解法一：map+數(shù)組

利用 map 記錄每個(gè)元素出現(xiàn)的頻率，利用數(shù)組來比較排序元素

代碼實(shí)現(xiàn)：

let topKFrequent = function(nums, k) { 
    let map = new Map(), arr = [...new Set(nums)] 
    nums.map((num) => { 
        if(map.has(num)) map.set(num, map.get(num)+1) 
        else map.set(num, 1) 
    }) 
     
    return arr.sort((a, b) => map.get(b) - map.get(a)).slice(0, k); 
}; 

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(nlogn)
• 空間復(fù)雜度：O(n)

題目要求算法的時(shí)間復(fù)雜度必須優(yōu)于 O(n log n) ，所以這種實(shí)現(xiàn)不合題目要求

解法二：map + 小頂堆

遍歷一遍數(shù)組統(tǒng)計(jì)每個(gè)元素的頻率，并將元素值( key )與出現(xiàn)的頻率( value )保存到 map 中

通過 map 數(shù)據(jù)構(gòu)建一個(gè)前 k 個(gè)高頻元素小頂堆，小頂堆上的任意節(jié)點(diǎn)值都必須小于等于其左右子節(jié)點(diǎn)值，即堆頂是最小值。

具體步驟如下：

• 遍歷數(shù)據(jù)，統(tǒng)計(jì)每個(gè)元素的頻率，并將元素值( key )與出現(xiàn)的頻率( value )保存到 map 中
• 遍歷 map ，將前 k 個(gè)數(shù)，構(gòu)造一個(gè)小頂堆
• 從 k 位開始，繼續(xù)遍歷 map ，每一個(gè)數(shù)據(jù)出現(xiàn)頻率都和小頂堆的堆頂元素出現(xiàn)頻率進(jìn)行比較，如果小于堆頂元素，則不做任何處理，繼續(xù)遍歷下一元素;如果大于堆頂元素，則將這個(gè)元素替換掉堆頂元素，然后再堆化成一個(gè)小頂堆。
• 遍歷完成后，堆中的數(shù)據(jù)就是前 k 大的數(shù)據(jù)

代碼實(shí)現(xiàn)：

let topKFrequent = function(nums, k) { 
    let map = new Map(), heap = [,] 
    nums.map((num) => { 
        if(map.has(num)) map.set(num, map.get(num)+1) 
        else map.set(num, 1) 
    }) 
     
    // 如果元素?cái)?shù)量小于等于 k 
    if(map.size <= k) { 
        return [...map.keys()] 
    } 
     
    // 如果元素?cái)?shù)量大于 k，遍歷map，構(gòu)建小頂堆 
    let i = 0 
    map.forEach((value, key) => { 
        if(i < k) { 
            // 取前k個(gè)建堆, 插入堆 
            heap.push(key) 
            // 原地建立前 k 堆 
            if(i === k-1) buildHeap(heap, map, k) 
        } else if(map.get(heap[1]) < value) { 
            // 替換并堆化 
            heap[1] = key 
            // 自上而下式堆化第一個(gè)元素 
            heapify(heap, map, k, 1) 
        } 
        i++ 
    }) 
    // 刪除heap中第一個(gè)元素 
    heap.shift() 
    return heap 
}; 
 
// 原地建堆，從后往前，自上而下式建小頂堆 
let buildHeap = (heap, map, k) => { 
    if(k === 1) return 
    // 從最后一個(gè)非葉子節(jié)點(diǎn)開始，自上而下式堆化 
    for(let i = Math.floor(k/2); i>=1 ; i--) { 
        heapify(heap, map, k, i) 
    } 
} 
 
// 堆化 
let heapify = (heap, map, k, i) => { 
    // 自上而下式堆化 
    while(true) { 
        let minIndex = i 
        if(2*i <= k && map.get(heap[2*i]) < map.get(heap[i])) { 
            minIndex = 2*i 
        } 
        if(2*i+1 <= k && map.get(heap[2*i+1]) < map.get(heap[minIndex])) { 
            minIndex = 2*i+1 
        } 
        if(minIndex !== i) { 
            swap(heap, i, minIndex) 
            i = minIndex 
        } else { 
            break 
        } 
    } 
} 
 
// 交換 
let swap = (arr, i , j) => { 
    let temp = arr[i] 
    arr[i] = arr[j] 
    arr[j] = temp 
} 

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：遍歷數(shù)組需要 O(n) 的時(shí)間復(fù)雜度，一次堆化需要 O(logk) 時(shí)間復(fù)雜度，所以利用堆求 Top k 問題的時(shí)間復(fù)雜度為 O(nlogk)
• 空間復(fù)雜度：O(n)

解法三：桶排序

這里取前k個(gè)高頻元素，使用計(jì)數(shù)排序不再適合，在上題目中使用計(jì)數(shù)排序，將 i 元素出現(xiàn)的次數(shù)存儲(chǔ)在 bucket[i] ，但這種存儲(chǔ)不能保證 bucket 數(shù)組上值是有序的，例如 bucket=[0,3,1,2] ，即元素 0 未出現(xiàn)，元素 1 出現(xiàn) 3 次，元素 2 出現(xiàn) 1 次，元素 3 出現(xiàn) 2 次，所以計(jì)數(shù)排序不適用于取前k個(gè)高頻元素，不過，不用怕，計(jì)數(shù)排序不行，還有桶排序。

桶排序是計(jì)數(shù)排序的升級(jí)版。它也是利用函數(shù)的映射關(guān)系。

桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排)。

• 首先使用 map 來存儲(chǔ)頻率
• 然后創(chuàng)建一個(gè)數(shù)組(有數(shù)量的桶)，將頻率作為數(shù)組下標(biāo)，對(duì)于出現(xiàn)頻率不同的數(shù)字集合，存入對(duì)應(yīng)的數(shù)組下標(biāo)(桶內(nèi))即可。

代碼實(shí)現(xiàn)：

let topKFrequent = function(nums, k) { 
    let map = new Map(), arr = [...new Set(nums)] 
    nums.map((num) => { 
        if(map.has(num)) map.set(num, map.get(num)+1) 
        else map.set(num, 1) 
    }) 
     
    // 如果元素?cái)?shù)量小于等于 k 
    if(map.size <= k) { 
        return [...map.keys()] 
    } 
     
    return bucketSort(map, k) 
}; 
 
// 桶排序 
let bucketSort = (map, k) => { 
    let arr = [], res = [] 
    map.forEach((value, key) => { 
        // 利用映射關(guān)系（出現(xiàn)頻率作為下標(biāo)）將數(shù)據(jù)分配到各個(gè)桶中 
        if(!arr[value]) { 
            arr[value] = [key] 
        } else { 
            arr[value].push(key) 
        } 
    }) 
    // 倒序遍歷獲取出現(xiàn)頻率最大的前k個(gè)數(shù) 
    for(let i = arr.length - 1;i >= 0 && res.length < k;i--){ 
        if(arr[i]) { 
            res.push(...arr[i]) 
        } 
 } 
 return res 
} 

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

leetcode：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/javascript-qian-k-ge-gao-pin-yuan-su-by-user7746o/