347. Top K Frequent Elements

Leetcode 問題: 347. Top K Frequent Elements
Categories:
Tags:

題目

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

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]

Input: nums = [-1, -1], k = 1
Output: [-1]

答案

JavaScript

  1. 先找出所有數字出現的頻率有多少，產生 數字出現頻率 Map
  2. 將數字出現頻率 Map 反轉，以頻率當作 key，產生出，頻率有哪些數字 Map
  3. 從較高頻率往較低頻率找，逐漸將前 k 頻率排名加入清單中
/**
 * @param {number[]} numsList
 * @param {number} topKFrequency
 * @return {number[]}
 */
var topKFrequent = function(numsList, topKFrequency) {
    // 數字頻率對應 Map
    const numberFrequencyMap = new Map();
    // 最大數字出現頻率
    let maxFrequency = 1;

    // 取得每個數字出現頻率對應 Mapping
    numsList.forEach((currentNumber, numberIndex) => {
        // 如果沒有此對應數字，設定預設數字頻率為 1
        let numberFrequency = 1;

        if (numberFrequencyMap.has(currentNumber)) {
            // 如果有此對應數字，將頻率數字 ++
            numberFrequency = numberFrequencyMap.get(currentNumber) + 1;
        }
        if (maxFrequency < numberFrequency) {
            // 如果有更高的出現頻率，設定為目前最高頻率
            maxFrequency = numberFrequency;
        }
        // 設定數字頻率
        numberFrequencyMap.set(currentNumber, numberFrequency);
    });


    // 取得對應頻率，所有數字陣列資料
    const frequencyNumberBucketMap = new Map();
    numberFrequencyMap.forEach((numberFrequency, num) => {
        let numberFrequencyBucket = [];
        if (frequencyNumberBucketMap.has(numberFrequency)) {
            // 如果有此對應數字，將頻率數字 ++
            numberFrequencyBucket = frequencyNumberBucketMap.get(numberFrequency);
        }
        // 將目前數字加入此頻率陣列
        numberFrequencyBucket.push(num);
        // 設定頻率陣列
        frequencyNumberBucketMap.set(numberFrequency, numberFrequencyBucket)
    });


    // Top K 頻率出現最高的數字清單
    let TopKNumberList = [];
    // 取得 Top K 頻率出現最高的數字
    for (let checkFrequency = maxFrequency; checkFrequency >= 1; checkFrequency--) {
        if (!frequencyNumberBucketMap.has(checkFrequency)) {
            // 如果沒有找到此頻率數字，繼續找下一個
            continue;
        }

        // 取得此頻率數字清單
        let numberFrequencyBucket = frequencyNumberBucketMap.get(checkFrequency);

        for (let i in numberFrequencyBucket) {
            let currentNumber = numberFrequencyBucket[i];
            if (TopKNumberList.length >= topKFrequency) {
                // 如果已經有足夠的清單了，跳離開迴圈，不需要再尋找
                break;
            }

            // 將此數字加入 Top k 清單中
            TopKNumberList.push(currentNumber);
        }

        if (TopKNumberList.length >= topKFrequency) {
            // 如果已經有足夠的清單了，跳離開迴圈，不需要再尋找
            break;
        }
    }

    return TopKNumberList;
};

參考資料