前k个高频元素

题目

题目来源：力扣（LeetCode）

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

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

示例 2:

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

方法一：快速排序

我们可以使用基于快速排序的方法，求出「出现次数数组」的前 k 大的值。

1. 首先用哈希表记录每个数字出现的次数
2. 对每个数及对应次数通过快排进行排序，返回前k个
3. 在对数组 arr[l…r] 做快速排序的过程中，我们首先将数组划分为两个部分 arr[i…q−1] 与 [q+1…j]，并使得 arr[i…q−1] 中的每一个值都不超过 arr[q]，且 arr[q+1…j] 中的每一个值都大于arr[q]。

于是，我们根据 k 与左侧子数组 arr[i…q−1] 的长度（为q−i）的大小关系：

• 如果 k≤q−i，则数组 arr[l…r] 前 k 大的值，就等于子数组 arr[i…q−1] 前 k 大的值。
• 否则，数组arr[l…r] 前 k 大的值，就等于左侧子数组全部元素，加上右侧子数组 arr[q+1…j] 中前 k−(q−i) 大的值。

/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function (nums, k) {
    // 统计出现次数
    const map = {};
    for (const n of nums) {
        n in map || (map[n] = 0);
        map[n]++;
    }
    const list = Object.entries(map);
    quickSelect(list, k, 0, list.length - 1, function (item, pivot) {
        return item[1] >= pivot[1];
    });
    return list.slice(0, k).map(el => el[0]);
};
/**
* 把 arr[r] 当成是 pivot
* 把大于等于 pivot 的数字放到左边
* 把小于 pivot 的数字放到右边
* @param {number[]} arr
* @param {number} l
* @param {number} r
*/
function partition(arr, l, r, comparator) {
    if (typeof comparator != 'function') {
        comparator = function (num, pivot) {
            return num >= pivot;
        };
    }
    let i = l;
    for (let j = l; j < r; j++) {
        if (comparator(arr[j], arr[r])) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    // 将 pivot 换到分界点
    [arr[i], arr[r]] = [arr[r], arr[i]];
    // 返回 pivot 的下标
    return i;
}
/**
* 寻找第 k 大元素
* 如果 pivot 的下标刚好是 k - 1，那我们就找到了
* 如果下标大于 k - 1，那就在 [left, pivotIndex - 1] 这段找第 k 大元素
* 如果下标小于 k - 1，那就对 [pivotIndex + 1, right] 这段找第 k - pivotIndex + left
- 1 大元素
* @param {number[]} list
* @param {number} left
* @param {number} right
* @param {number} k
* @param {function} comparator
*/
function quickSelect(list, k, left = 0, right = list.length - 1, comparator) {
    if (left >= right) return list[left];
    const pivotIndex = partition(list, left, right, comparator);
    if (pivotIndex - left === k - 1) return list[pivotIndex];
    else if (pivotIndex - left > k - 1)
        return quickSelect(list, k, left, pivotIndex - 1, comparator);
    else {
        return quickSelect(
            list,
            k - pivotIndex + left - 1,
            pivotIndex + 1,
            right,
            comparator,
        );
    }   
}