P4855 统计个数（入门）

解题思路

第一步，理解题意。 小鹿输入一串整数，最后一个数字是 -1，表示输入结束。-1 是"停止信号"，不是真正的数字。然后第二行再输入一个整数 n，我们要统计这串数字里 n 一共出现了多少次。

第二步，思考顺序。 注意：要找的数字 n 是第二行才输入的，可第一行的数字在一开始就陆续读进来了。所以不能一边读一边数，必须先开一个数组把第一行的所有数字存起来，读完之后再读 n，最后从头到尾扫一遍数组去数。

第三步，读取并存储。 用一个数组 a 和计数器 cnt。用一个死循环不断读整数 x：如果 x 等于 -1，就用 break 跳出循环，停止读入；否则把 x 存进 a[cnt]，cnt 加 1。数组 a 开成 100005 的大小，足够装下题目可能出现的数字个数，不会越界。

第四步，统计次数。 读入要查找的 n 后，用循环从第 0 个到第 cnt-1 个挨个检查：只要 a[i] 等于 n，答案变量 ans 就加 1。最后输出 ans。

第五步，边界情况。 如果第一行只有 -1（一个数字都没有），cnt 是 0，答案就是 0；如果 n 一次都没出现，答案也是 0。题目没说数字一定是正数，我们的程序用整数比较，正数和负数都能正确统计。举个例子：第一行是 6 1 2 3 4 6 5 3 3 2 1 3 -1，第二行 n=3，扫一遍发现有 4 个 3，输出 4，和样例一致。

参考代码

// 统计个数：输入一串数字直到-1，统计其中n出现几次
#include <iostream>
using namespace std;
int main() {
    int a[100005];    // 存输入的数字
    int cnt = 0;
    int x;
    while (true) {
        cin >> x;
        if (x == -1) break;   // 遇到-1停止输入
        a[cnt++] = x;
    }
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 0; i < cnt; i++)
        if (a[i] == n) ans++;
    cout << ans << endl;
    return 0;
}

复杂度分析

时间复杂度：读入是 O(cnt)，扫描统计是 O(cnt)，总时间是 O(cnt)，其中 cnt 是第一行数字的个数。

空间复杂度：需要一个数组存下所有数字，是 O(cnt)。