数据结构与算法 / 系统课时

哈希映射解决计数问题

哈希映射解决计数问题

许多问题不仅要知道元素是否出现,还要记录出现次数、下标或所属分组。本课用一个主示例展示频次统计和两数之和,归纳哈希映射中“键和值分别保存什么”的设计方法。

学习目标

  • 使用哈希映射统计元素出现频次。
  • 选择次数、下标或列表作为映射值。
  • 掌握两数之和中的补数查找与先查后存顺序。

先设计键和值

频次统计使用“元素到次数”的映射,每读到一次就把计数加一。索引问题可使用“元素到下标”的映射;若要保留全部位置,值应改为下标列表。

两数之和扫描当前值时,需要寻找 target - value。映射只保存此前见过的值与下标,先查询补数,再保存当前元素,才能避免把同一位置使用两次。

哈希映射的频次统计与补数查找模式

主示例:计数与两数之和

示例先用字典完成频次统计,再从统计结果中找最高频元素;随后使用“已见值到下标”的映射在线性扫描中完成两数之和。

python
from typing import Optional

def frequency_map(values: list[str]) -> dict[str, int]:
    counts: dict[str, int] = {}

    for value in values:
        # get 的默认值 0 表示该元素此前尚未出现
        counts[value] = counts.get(value, 0) + 1

    return counts

def most_common(counts: dict[str, int]) -> tuple[str, int]:
    if not counts:
        raise ValueError("counts 不能为空")
    return max(counts.items(), key=lambda item: item[1])

def two_sum(nums: list[int], target: int) -> Optional[tuple[int, int]]:
    seen_index: dict[int, int] = {}

    for index, value in enumerate(nums):
        complement = target - value

        # 先查后存,保证不会复用当前元素
        if complement in seen_index:
            return seen_index[complement], index
        seen_index[value] = index

    return None

def main() -> None:
    words = ["array", "hash", "array", "stack", "hash", "array"]
    counts = frequency_map(words)
    print("频次:", counts)
    print("最高频:", most_common(counts))

    nums = [2, 7, 11, 15]
    print("两数之和下标:", two_sum(nums, 9))

if __name__ == "__main__":
    main()

预期输出

text
频次: {'array': 3, 'hash': 2, 'stack': 1}
最高频: ('array', 3)
两数之和下标: (0, 1)

复杂度与关键边界

频次统计和两数之和都只扫描一次输入,哈希查询与写入平均为 O(1),所以平均时间复杂度为 O(n),额外空间为 O(n)。若使用双重循环寻找两数,时间复杂度会升为 O(n²)。

映射值应服从问题目标:需要首次下标时不要持续覆盖,需要最近下标时可以更新,需要全部下标时应保存列表。两数之和存在多个答案时,还要事先明确返回任意一组、第一组还是全部组合。

most_common 在最高次数并列时返回字典迭代中先出现的元素。本例没有并列;若业务要求固定的并列规则,应显式增加第二排序条件。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

哈希映射解决计数问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通