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

参考资料