青训/难题：查找热点数据问题-测试示例错了 更改如下

问题描述

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。请按升序排列。

1 <= nums.length <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
你所设计算法的时间复杂度必须优于 O(n log n)，其中 n 是数组大小。

示例- error

def solution(nums, k):
    # Please write your code here
    return -2

if __name__ == "__main__":
    #  You can add more test cases here
    print(solution( [1,1,1,2,2,3], 2) == "1,2" )
    print(solution( [1], 1) == "1" )
    

示例 -right

def solution(nums, k):
    # Please write your code here
    return -2

if __name__ == "__main__":
    #  You can add more test cases here
    print(solution( [1,1,1,2,2,3], 2) == [1, 2] )
    print(solution( [1], 1) == [1] )
    

思路：

需要把所有内容数量获取(计数)，再排序，2个步骤，才能得出前k个热点

使用map？ String，int？ 对map进行key及value排序

详细：

1、计数过程 Counter方法(偷懒操作)/基础的字典来实现计数功能

2、排序过程 最小堆

答案- 偷懒版本 是用Counter操作

from collections import Counter
import heapq


import heapq

def solution(nums, k):
    if not nums:
        return []
    
    # 使用Counter统计每个数字的频率
    freq_map = Counter(nums)
    
    # 使用堆来获取前k个最频繁的元素
    heap = []
    for num, freq in freq_map.items():
        if len(heap) < k:
            heapq.heappush(heap, (freq, num))
        else:
            if freq > heap[0][0]:
                heapq.heapreplace(heap, (freq, num))
    
    # 获取结果并按数字大小排序
    return sorted([pair[1] for pair in heap])

if __name__ == "__main__":
    #  You can add more test cases here
    print(solution( [1,1,1,2,2,3], 2) == [1, 2] )
    print(solution( [1], 1) == [1] )

答案-详细注释 含堆解释 但没有拆分Counter操作

from collections import Counter  # Counter是一个计数器工具，能自动统计元素出现次数
import heapq  # heapq是Python的堆操作模块，提供了堆队列算法


def solution(nums, k):
    if not nums:
        return []

    # Counter用法示例：Counter([1,1,1,2,2,3]) 会得到 {1:3, 2:2, 3:1}
    # 表示1出现3次，2出现2次，3出现1次
    freq_map = Counter(nums)
    print("频率统计结果:", dict(freq_map))  # 转成字典打印更直观

    # 堆（heap）是一种特殊的完全二叉树
    # Python中的heapq实现的是最小堆，即堆顶元素永远是最小的
    # 我们将存储(频率, 数字)的元组，这样就能按频率排序
    heap = []

    print("\n构建堆的过程:")
    for num, freq in freq_map.items():
        if len(heap) < k:
            # heappush将元素加入堆中，并保持堆的性质
            heapq.heappush(heap, (freq, num))
            print(f"将({freq}, {num})加入堆，当前堆:", heap)
        else:
            # heap[0]永远是最小的元素
            if freq > heap[0][0]:
                # heapreplace弹出最小的元素，并将新元素加入堆
                old = heap[0]
                heapq.heapreplace(heap, (freq, num))
                print(f"替换堆中最小元素{old}为({freq}, {num})，当前堆:", heap)

    # 最后堆中的元素就是出现频率最高的k个数
    # 我们只需要数字部分，即每个元组的第二个元素
    result = [pair[1] for pair in heap]
    print("\n堆中的元素(频率,数字):", heap)
    print("提取数字部分:", result)

    # 按数字大小排序
    result.sort()
    print("最终排序结果:", result)

    return result


# 测试代码
if __name__ == "__main__":
    test_nums = [1, 1, 1, 2, 2, 3]
    k = 2
    print("测试输入:", test_nums, "k=", k)
    result = solution(test_nums, k)
    print("最终输出:", result)

答案- 拆解Counter 和 最小堆

基础的字典来实现计数功能

import heapq

def solution(nums, k):
    if not nums:
        return []
    
    # 1. 统计频率
    freq_map = {}
    for num in nums:
        if num in freq_map:
            freq_map[num] = freq_map[num] + 1
        else:
            freq_map[num] = 1
    print("频率统计结果:", freq_map)  # 例如：{1: 3, 2: 2, 3: 1}
    
    # 2. 构建最小堆，存储格式：(频率, 数字)
    heap = []
    print("\n构建堆的过程:")
    for num, freq in freq_map.items():
        print(f"处理数字{num}, 其频率为{freq}")
        if len(heap) < k:
            # 堆未满，直接加入
            heapq.heappush(heap, (freq, num))
            print(f"堆未满，将(频率{freq}, 数字{num})加入堆，当前堆:", heap)
        else:
            # 堆已满，且当前频率大于堆顶的频率时才替换
            # heap[0][0]是堆顶元素的频率
            if freq > heap[0][0]:
                old = heap[0]
                heapq.heapreplace(heap, (freq, num))
                print(f"堆已满，将堆顶(频率{old[0]}, 数字{old[1]})替换为(频率{freq}, 数字{num})，当前堆:", heap)
            else:
                print(f"频率{freq}小于等于堆顶频率{heap[0][0]}，跳过")
    
    # 3. 提取结果并排序
    result = sorted([pair[1] for pair in heap])
    print("\n堆中最终的元素(频率,数字):", heap)
    print("提取数字并排序后:", result)
    
    return result

# 测试代码
if __name__ == "__main__":
    nums = [1,1,1,2,2,3]  # 测试数组
    k = 2  # 找出现频率最高的2个数
    print("测试输入:", nums, "k=", k)
    result = solution(nums, k)
    print("最终输出:", result)

# 测试代码
if __name__ == "__main__":
    test_cases = [
        ([1,1,1,2,2,3], 2),  # 应该返回 [1,2]
        ([1], 1),            # 应该返回 [1]
    ]
    
    for nums, k in test_cases:
        print("\n测试输入:", nums, "k=", k)
        result = solution(nums, k)
        print("最终输出:", result)

关键概念补充

Counter

Counter 是 Python 的一个计数器类
它可以自动统计序列中每个元素出现的次数
例如：Counter([1,1,1,2,2,3]) 会返回 {1:3, 2:2, 3:1}

堆 Heap

堆（Heap）

堆是一种特殊的树形数据结构
Python 的 heapq 实现的是最小堆，即：

堆顶元素（索引0）永远是最小的
任何父节点都小于其子节点

主要操作：

heappush: 将元素加入堆
heapreplace: 替换堆顶元素