{ }codelper

学习 › C

进阶 · 24

计数、累计、分组

遍历一次：数出符合条件的个数，带着“到目前为止”的值，按键把数据归到一起。

计数、累计、分组是遍历一次数据、边走边得出答案的三种基本形式。
下面的示例逐个查看分数，输出到目前为止的总和与最高分，数出有几个分数在 80 分以上，再把分数按十位分组（60 多分、70 多分……）输出。

#include <stdio.h> int main(void) {    int scores[100], n = 0;    while (n < 100 && scanf("%d", &scores[n]) == 1) n++;    int count = 0;          // 80점 이상인 점수의 개수    int total = 0;          // 지금까지의 합    int best = scores[0];   // 지금까지의 최고 점수    // 사전이 없어서 묶음을 배열로: groups[6]이 60점대(점수는 0~100), sizes[6]이 그 개수    int groups[11][100], sizes[11] = {0};    for (int i = 0; i < n; i++) {        int s = scores[i];        if (s >= 80) count++;        total += s;        if (s > best) best = s;        printf("%d %d\n", total, best);        int key = s / 10;        groups[key][sizes[key]++] = s;    }    printf("%d\n", count);    for (int key = 0; key <= 10; key++) {        if (sizes[key] == 0) continue;   // 비어 있는 묶음은 건너뛰어요        printf("%d:", key * 10);        for (int j = 0; j < sizes[key]; j++) printf(" %d", groups[key][j]);        printf("\n");    }    return 0;}
stdin
72 85 90 68 85 77 93
stdout
72 72
157 85
247 90
315 90
400 90
477 90
570 93
4
60: 68
70: 72 77
80: 85 85
90: 90 93

要点

  • 计数从 0 开始，只有符合条件时才加 1。
    和求和不同，加的不是值，而是 1。
  • 累计值是每看一个元素就更新一次的变量。
    到目前为止的总和（total）、到目前为止的最高分（best）始终保存着“到这里为止的答案”，所以中途就能输出结果。
    循环单元里的 total += i 就是这种形式。
  • 累计变量要在循环之前创建。
    个数与总和从 0 开始，最大、最小值从第一个值开始。
  • 分组是给每个值定一个键（示例中 68 → 60，72 → 70），再把值放进字典里这个键对应的列表。
    计数的字典（字典单元）里值是数，分组的字典里值是列表。
  • 第一次见到的键还没有列表。
    要先放进一个空列表，再往里添加值。
  • 不必分三次遍历。
    示例在一个循环里同时完成计数、累计和分组。

各语言的写法

Python计数用 count += 1（一行写法：sum(1 for s in scores if s >= 80)），累计用 total += s。
分组像示例那样先 if key not in groups: groups[key] = []，再 groups[key].append(s)；简短写法是 groups.setdefault(key, []).append(s) 或 collections.defaultdict(list)
JavaScript计数用 count++（一行写法：scores.filter((s) => s >= 80).length），累计用 total += s。
分组用 Map：先 if (!groups.has(key)) groups.set(key, []);，再 groups.get(key).push(s)
TypeScript和 JavaScript 一样，并像 new Map<number, number[]>() 这样写上类型。
groups.get(key) 的类型可能是 undefined，直接 .push 会报类型错误（TS2532）。
要像示例那样把取出的值放进变量，确认不是 undefined 再用
Java计数用 count++（一行写法：scores.stream().filter(s -> s >= 80).count()），累计用 total += s。
分组用 Map<Integer, List<Integer>>：用 containsKey 检查后 put(key, new ArrayList<>())；简短写法是 groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s)。
用 TreeMap 就按键的顺序遍历
C#计数用 count++（LINQ 写法：scores.Count(s => s >= 80)），累计用 total += s。
分组用 Dictionary<int, List<int>>：先 if (!groups.ContainsKey(key)) groups[key] = new List<int>();，再 groups[key].Add(s)。
用 SortedDictionary 就按键的顺序遍历
C++计数用 count++（<algorithm> 里也有 std::count_if），累计用 total += s。
分组用 std::map<int, std::vector<int>>，只要一行 groups[key].push_back(s)。
键不存在时，[] 会自动创建一个空的 vector
C计数和累计与其他语言相同（count++、total += s）。
没有字典，所以分组要自己动手。
键是较小的整数时，像示例那样用二维数组 groups[key][sizes[key]++] = s 存放，并另外记下每组的个数（sizes）
Craykon计数用 count++，累计用 total += s。
分组用 字典()：先 如果 (!groups.包含(key)) { groups[key] = []; }，再 groups[key].添加(s)。
要按键的顺序输出，就把 groups.键列表 用 排序() 排好再遍历

常见错误

把 += 写成了 =+

int count = 0;
int scores[] = {72, 85, 90};
for (int i = 0; i < 3; i++)
    if (scores[i] >= 80) count =+ 1;
printf("%d\n", count);

→ 1 — 没有报错，但结果不是 2。count =+ 1 就是 count = +1，意思是“存入 1”

写成 count += 1。
如果个数总是 1，先检查这两个字符的顺序。

在循环里把累计变量设成 0

const scores = [72, 85, 90];
for (const s of scores) {
  let total = 0;
  total += s;
  console.log(total);
}

→ 72、85、90 — 每一轮都回到 0，总和累积不起来

total 的初始值（0）只在循环之前给一次，循环里只做加法。
Python 和 Craykon 没有 let、int 这样的声明词，但只要 total = 0 写在循环里，同样会输出 72、85、90。

没有先建空列表就往分组里放Java

Map<Integer, List<Integer>> groups = new TreeMap<>();
int s = 68;
int key = s / 10 * 10;
groups.get(key).add(s);

→ NullPointerException — 键不存在，get 返回了 null

先写 if (!groups.containsKey(key)) groups.put(key, new ArrayList<>());，或者写成 groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s)。

各语言的差异
每个分组都要有各自的列表。
在 Python 中用 groups = dict.fromkeys([60, 70], []) 预先建好键，所有键会共用同一个列表，把 68 和 72 分别放进不同的键，结果却是 {60: [68, 72], 70: [68, 72]}。
要像示例那样，每次遇到新的键都新建一个 []。

练习题

  1. 不低于平均的早晨8P0343
  2. 直到 0 的累计和8P0051
  3. 按首字母分组8P0066
  4. 数位数8P0052
  5. 凑满 k 人就出发的体验摊位8P0349
  6. 最佳连续区间的平均值8P0106
  7. 反转选课名单1P0123
  8. 问卷回答竖直柱状图8P0150