LeetCode 补充题 168. 汉字总频次与文档频次统计

2026-09-13 HGNULB 约 5 分钟

文章信息 3 个分类 1 个标签

分类

补充题中等新浪

题目描述

给定多篇文本 documents，统计每个汉字的总出现次数，以及包含该汉字的文本篇数。

按包含篇数从高到低返回统计记录；相同篇数的记录顺序不限。

示例 1：

输入： documents = ["人人爱AI","人爱学"]
输出： [(人,3,2),(爱,2,2),(学,1,1)]
解释： 每条记录依次为汉字、总次数、包含篇数；前两条可以交换。

示例 2：

输入： documents = ["ABC123",""]
输出： []
解释： 没有汉字，返回空结果。

提示：

按 Unicode Han 字符集合识别汉字，标点、数字和拉丁字母不统计。
一篇文本内出现多次只增加一次文档频次，但总频次应全部累计。
每行一篇的文件可逐行读入，返回记录可逐行写出。

题意分析

总频次按每次出现累计，文档频次只关心一篇中是否出现过。同一个字在某篇重复很多次不能提高其文档频次，因此需要全局统计表与每篇独立的去重集合。

解法：全局频次与单篇去重

核心思路

[!blue]

按 Unicode 码点遍历文本，只让 Han 集合中的字符参与统计。对每次汉字出现，无条件将全局记录的 total 加 1；仅当它第一次进入本篇的 seen 集合时，才将 documents 加 1。

进入下一篇时重新创建 seen，这样同一字在另一篇出现仍会贡献一次文档数。总次数使用 64 位累加，字符身份用码点保存，避免拆开补充平面的汉字。

最后只对不同汉字的统计记录排序，首先按文档数降序，同篇数时按码点升序使结果确定；后者满足题面允许任意同分顺序的要求。没有汉字时返回空列表。

解题步骤

按 Unicode 码点筛选汉字，全局增加总频次。

每篇创建独立集合，首次出现该字时才增加文档数。

按文档数降序、并列按码点升序输出。

代码实现

class Solution {
    static class Stat {
        final int codePoint;
        long total;
        int documents;

        Stat(int cp) {
            codePoint = cp;
        }
    }

    public List<Stat> countHan(List<String> docs) {
        Map<Integer, Stat> stats = new HashMap<>();

        for (String text : docs) {
            Set<Integer> seen = new HashSet<>();

            text.codePoints()
                    .filter(cp -> Character.UnicodeScript.of(cp) == Character.UnicodeScript.HAN)
                    .forEach(
                            cp -> {
                                Stat s = stats.computeIfAbsent(cp, Stat::new);

                                s.total++;

                                if (seen.add(cp)) {
                                    s.documents++;
                                }
                            });
        }

        List<Stat> out = new ArrayList<>(stats.values());

        out.sort(
                Comparator.comparingInt((Stat s) -> s.documents)
                        .reversed()
                        .thenComparingInt(s -> s.codePoint));

        return out;
    }
}

import (
    "sort"
    "unicode"
)

type HanStat struct {
    Character rune
    Total     int64
    Documents int
}

func countHan(docs []string) []HanStat {
    stats := map[rune]*HanStat{}
    for _, text := range docs {
        seen := map[rune]bool{}
        for _, ch := range text {
            if !unicode.Is(unicode.Han, ch) {
                continue
            }
            if stats[ch] == nil {
                stats[ch] = &HanStat{Character: ch}
            }
            stats[ch].Total++
            if !seen[ch] {
                stats[ch].Documents++
                seen[ch] = true
            }
        }
    }
    out := make([]HanStat, 0, len(stats))
    for _, s := range stats {
        out = append(out, *s)
    }
    sort.Slice(out, func(i, j int) bool {
        if out[i].Documents != out[j].Documents {
            return out[i].Documents > out[j].Documents
        }
        return out[i].Character < out[j].Character
    })
    return out
}

复杂度分析

时间复杂度：设总码点数为 N，不同汉字数为 U，时间 $O(N+U \log U)$。

空间复杂度：辅助空间 $O(U)$。

关键点总结

[!green]

总频次累计每次出现，文档频次每篇最多累计一次；一个字在一篇重复十次仍只贡献一个文档。

易错点总结

[!yellow]

总频次与包含篇数不是一回事；按字节或 UTF-16 单个 char 遍历会拆开部分汉字。

相似题目

题目	难度	关联与区别
451. 根据字符出现频率排序	中等	同样先统计字符频次再排序，本题还区分总频次与文档频次，且限定 Unicode 汉字。
692. 前K个高频单词	中等	同样按频次排序并明确并列规则，本题统计字符的文档覆盖数，原题统计单词出现次数。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/108036035

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！