39. Top K Frequent Events with Order Preservation

Origin: HackerRank Prep Kit #39

题目描述

给定一个整数数组 events 和一个整数 k，返回出现频率最高的 k 个元素。如果两个元素频率相同，优先返回在原数组中首次出现更早的那个。

示例

Example 1

Input: events = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2] Explanation: 频率：1→3, 2→2, 3→1。前两个是 1 和 2。

Example 2

Input: events = [4, 2, 1, 2, 4, 1, 4, 2, 3], k = 3 Output: [2, 4, 1] Explanation: 频率：2→3, 4→3, 1→2, 3→1。频率最高的是 2 和 4（都 3 次），2 首次出现在 index 1，4 首次出现在 index 0… 实际 4 在 index 0 先出现。等等，看题目解释：2 频率 3 最高，4 频率 3 但首次出现更晚… 实际看题目原解：频率 2→3 最高，4→2、1→2、3→2 并列，按首次出现排序 4(index 0) > 1(index 2) > 3(index 5)，最终 [2, 4, 1]。

Sample Input 0

0 0

Output: []（空数组）

Sample Input 1

1 5 1

Output: [5]（只有一个元素 5，k=1）

约束

• 0 <= events.length <= 100000
• 0 <= events[i] <= 10
• 0 <= k <= events.length
• 如果 events.length > 0 则 1 <= k <= D（D 是不同元素个数）
• 如果 events.length = 0 则 k = 0

关键信息

• 频率相同按首次出现顺序排序（小的 index 优先）
• 需要记录每个元素的频率和首次出现位置
• 返回前 k 个

Resolution

我的解法

function getTopKFrequentEvents(events: number[], k: number): number[] {
    if (!events.length || k <= 0) return []
    let freMap = new Map()
    let firstIndex = new Map()
    for (let i = 0; i < events.length; i++) {
        const cur = events[i]
        if (freMap.has(cur)) {
            freMap.set(cur, freMap.get(cur) + 1)
        } else {
            freMap.set(cur, 1)
        }
        if (!firstIndex.has(cur)) {
            firstIndex.set(cur, i)
        }
    }
    const arr = Array.from(freMap.keys()).sort((keya, keyb) => {
        if (freMap.get(keyb) - freMap.get(keya) === 0) {
            return firstIndex.get(keya) - firstIndex.get(keyb)
        }
        return freMap.get(keyb) - freMap.get(keya)
    })
    const result = []
    for (let i = 0; i < k; i++) {
        result.push(arr[i])
    }
    return result
}

解题思路

Top K 高频元素（LeetCode 347 变体）。三步走：

1. 用 Map 统计每个元素频率，同时用 firstIndex Map 记录首次出现位置
2. 按频率降序排序，频率相同按首次出现 index 升序（tie-break）
3. 取前 k 个

踩坑

• JS sort 不保证稳定性，频率相同时不能依赖引擎默认行为，必须自己加 tie-break
• 第一版只按频率排序 AC 了，但没处理首次出现顺序，补上 firstIndex 后更严谨

复杂度

• 时间：O(n + m log m)，n 是数组长度，m 是不同元素个数
• 空间：O(m)