题目重点：从非零元素比例和访问模式选择稀疏表示，比较点查、遍历、插入及矩阵行运算的时间与空间。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 把‘稀疏阵’作为可一维或二维的稀疏数组/矩阵存储知识题；为比较明确假设有 N 个逻辑位置、k 个非默认元素，默认值为 0。
- 规模估算忽略容器额外对象头并单独提醒 Python/Java 哈希表实际成本可能高于理论元素数。
解题路线
- 若只需遍历非零项，坐标表存 (index,value) 或 (row,col,value)，O(k) 项；排序后可做流式归并，但随机点查要 O(log k) 二分或 O(k) 扫描。
- 高频随机读写可用坐标→值哈希表，期望 O(1) 点查/更新、O(k) 条目，但哈希和对象开销大，遍历顺序不稳定；删除恢复默认值要删键。
- 二维静态矩阵按行乘向量、顺序扫描，可用 CSR 的 row_ptr[n_rows+1]、col_idx[k]、values[k]；一行内列查二分，动态中间插入需搬移后续项，不适合大量原地更新。
- 密集数组直接 O(N) 空间、O(1) 下标访问，k/N 变大或访问高度随机时可能因连续内存更快。先按字节量估交叉点，再用真实读写比例基准测试。
手动走一遍
逻辑 100 万格、仅 100 个非零值：坐标表或哈希表只存约 100 项，密集表示必须为所有 100 万格分配槽。若是 1000×1000 矩阵按行做 SpMV，CSR 的 row_ptr 有 1001 项，可顺序定位每行非零段；若每秒不断随机插入，哈希更合适。
规模与取舍
坐标表 O(k) 条目、排序后点查 O(log k)；哈希 O(k) 条目、平均点查/更新 O(1)；CSR O(k+r) 条目，整矩阵非零遍历 O(k+r)，其中 r 为行数；密集 O(N) 空间。实际字节成本依整数宽度与容器实现。
易错点与追问
容易失分的边界
- 只说‘用 HashMap’，没有问点查还是行扫描。
- 把二维 CSR 与一维稀疏向量实现混为一个固定接口。
- 声称稀疏一定省内存，忽略坐标和哈希开销。
- 遗漏默认零的语义及显式存零如何处理。
继续深挖
- 若更新比读取多，CSR 还合适吗？
- 稀疏向量点积怎样避免扫描所有 N 个位置？
- 同一坐标重复写入如何保留最后值？
- k/N 多大时应改回密集表示？
