小红背单词

思路

题意很直接：小红按顺序背单词，当她已经记住了 k 个单词时，一个新单词需要出现 k+1 次才能记住。问最终记住了多少个单词？

那我们怎么模拟这个过程呢？

关键观察：我们需要追踪两个东西——每个单词累计出现了几次，以及当前已经记住了几个单词（也就是"记忆门槛"）。

模拟过程：遍历输入序列，对每个单词：

  1. 如果已经记住了，跳过（不需要再背了）
  2. 否则把它的出现次数 +1
  3. 检查出现次数是否达到了门槛 total + 1（total 是当前已记住的单词数），达到了就记住它，total++

拿示例来走一遍：输入 you thank queue queue thank

  • "you"：出现 1 次，门槛 0+1=1，达到了，记住！total=1
  • "thank"：出现 1 次，门槛 1+1=2，没达到
  • "queue"：出现 1 次，门槛 1+1=2，没达到
  • "queue"：出现 2 次，门槛 1+1=2，达到了，记住！total=2
  • "thank"：出现 2 次，门槛 2+1=3，没达到

最终答案是 2，符合预期。

有个细节值得注意：当一个单词被记住后，门槛立刻变高了。所以后面的单词更难被记住——这就是为什么 "thank" 虽然也出现了 2 次，但因为门槛已经涨到了 3，所以没记住。

用哈希表统计次数，哈希集合记录已记住的单词，一遍扫描就搞定了。

代码

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_map<string, int> cnt;
    unordered_set<string> memorized;
    int total = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (memorized.count(s)) continue;
        cnt[s]++;
        if (cnt[s] >= total + 1) {
            memorized.insert(s);
            total++;
        }
    }
    cout << total << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<String, Integer> cnt = new HashMap<>();
        Set<String> memorized = new HashSet<>();
        int total = 0;
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            if (memorized.contains(s)) continue;
            cnt.merge(s, 1, Integer::sum);
            if (cnt.get(s) >= total + 1) {
                memorized.add(s);
                total++;
            }
        }
        System.out.println(total);
    }
}

import sys
input = sys.stdin.readline
n = int(input())
cnt = {}
memorized = set()
total = 0
for _ in range(n):
    w = input().strip()
    if w in memorized:
        continue
    cnt[w] = cnt.get(w, 0) + 1
    if cnt[w] >= total + 1:
        memorized.add(w)
        total += 1
print(total)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const cnt = new Map();
    const memorized = new Set();
    let total = 0;
    for (let i = 1; i <= n; i++) {
        const w = lines[i];
        if (memorized.has(w)) continue;
        cnt.set(w, (cnt.get(w) || 0) + 1);
        if (cnt.get(w) >= total + 1) {
            memorized.add(w);
            total++;
        }
    }
    console.log(total);
});

复杂度

  • 时间复杂度：，扫一遍输入，哈希操作均摊 。
  • 空间复杂度：，哈希表和集合最多存 n 个不同的单词。

总结

这题本质上就是一个带动态门槛的计数模拟。门槛随着记住的单词数增长，所以先出现的单词更容易被记住。用哈希表统计出现次数，遇到达标的就记住并抬高门槛，一遍过。思路清晰的话代码很短。