小红背单词

[题目链接](https://www.nowcoder.com/practice/b3d0fa1c43c44e0580654cb93c1bfdb9)

思路

题意理解

小红按顺序背单词。如果她当前已经记住了 $k$ 个单词，那么她需要遇到某个未记住的新单词 $k+1$ 次才能记住它。

初始 $k = 0$ ，第一个未见过的单词只需出现 $1$ 次就能记住。
记住第一个后 $k = 1$ ，下一个未记住的单词需要出现 $2$ 次。
以此类推。

已经记住的单词再次出现时直接跳过，不需要任何处理。

模拟过程

从前到后扫描单词序列，用一个哈希表记录每个未记住的单词当前出现了多少次，用一个集合记录已经记住的单词。

对于当前单词 $s$ ：

如果 $s$ 已经记住，跳过。
否则将 $s$ 的出现次数加 $1$ 。
如果出现次数达到了 $k+1$ （ $k$ 为当前已记住的单词数），就把 $s$ 标记为已记住， $k$ 加 $1$ 。

最终输出 $k$ 即可。

样例演示

输入序列：you thank queue queue thank

步骤	单词	已记住数 $k$	需要次数 $k+1$	该词累计次数	是否记住
1	you	0	1	1	是
2	thank	1	2	1	否
3	queue	1	2	1	否
4	queue	1	2	2	是
5	thank	2	3	2	否

最终记住 $2$ 个单词。

复杂度分析

时间复杂度： $O(n)$ ，每个单词只做常数次哈希操作。
空间复杂度： $O(n)$ ，哈希表和集合最多存储 $n$ 个单词。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int memorized = 0;
    unordered_map<string,int> cnt;
    unordered_set<string> done;
    for(int i=0;i<n;i++){
        char buf[20];
        scanf("%s",buf);
        string s(buf);
        if(done.count(s)) continue;
        cnt[s]++;
        if(cnt[s] >= memorized+1){
            done.insert(s);
            memorized++;
        }
    }
    printf("%d\n",memorized);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int memorized = 0;
        HashMap<String, Integer> cnt = new HashMap<>();
        HashSet<String> done = new HashSet<>();
        for (int i = 0; i < n; i++) {
            String s = br.readLine().trim();
            if (done.contains(s)) continue;
            int c = cnt.getOrDefault(s, 0) + 1;
            cnt.put(s, c);
            if (c >= memorized + 1) {
                done.add(s);
                memorized++;
            }
        }
        System.out.println(memorized);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
memorized = 0
cnt = {}
done = set()
for _ in range(n):
    s = input().strip()
    if s in done:
        continue
    cnt[s] = cnt.get(s, 0) + 1
    if cnt[s] >= memorized + 1:
        done.add(s)
        memorized += 1
print(memorized)

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