【基础篇 - Day 20】 前 K 个高频元素

题目描述

入选理由

1. 哈希表用于频次计算

题目描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

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

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

加餐

215. 数组中的第 K 个最大元素

我的回答

解法一

时空复杂度

n 是数字的种数

时间复杂度：O(nlogn) 排序的复杂度

空间复杂度: O(n)

明天再看看传说中的顶堆

var topKFrequent = function (nums, k) {
    let map = {}
    nums.forEach(v => { map[v] = (map[v] || 0) + 1 })
    return Object.entries(map).sort((a, b) => b[1] - a[1]).slice(0, k).map(v => v[0])
};

解法二

时间复杂度：O(n) N 是数字种类

空间复杂度: O(n) Map 的空间

快速选择

const swap = (arr, a, b) => [arr[a], arr[b]] = [arr[b], arr[a]]
const quicklySelect = (arr, left, right, k) => {
    let random = Math.floor(Math.random() * (right - left) + left)
    swap(arr, right, random)
    let i = left
    let j = left
    while (j < right) {
        if (arr[j][1] > arr[right][1]) {
            swap(arr, i, j)
            i++
        }
        j++
    }
    swap(arr, i, j)
    if (i === k) return arr.slice(0, k)
    if (i > k) {
        return quicklySelect(arr, left, i - 1, k)
    }
    if (i < k) {
        return quicklySelect(arr, i + 1, right, k)
    }
}
var topKFrequent = function (nums, k) {
    let map = {}
    nums.forEach(v => { map[v] = (map[v] || 0) + 1 })
    let arr = Object.entries(map)
    return quicklySelect(arr, 0, arr.length - 1, k).map(v => v[0])
};

解法三

时间复杂度：O(logn)

空间复杂度: O(n) Map 的空间

堆 ，真的记不住

参考回答

• 官方题解