记录的时候用数组和哈希表有什么区别？

这是一个非常深入且具有实战意义的问题。在 NOI 竞赛中，选择数组还是哈希表，往往决定了你的程序是“稳过”还是“在超时的边缘疯狂试探”。

作为教练，我把这两者的区别总结为：“空间换时间的极致” vs “通用灵活性”。

---

一、 形象化类比：找房间

假设我们要存储每个数字的“大哥”是谁。

1. 数组（Array）：像是一条整齐的街道

• 做法：数字是几，你就去几号房。比如数字是 100，你就直接推开 100 号房的门，把大哥的名字存进去。
• 特点：推门即达。你不需要查表，不需要询问。
• 条件：街道必须足够长（值域范围 MAXV 不能太大）。

2. 哈希表（unordered_map）：像是一个写字楼的咨询台

• 做法：你拿着数字 100 去问前台：“请问 100 对应的记录在哪里？”前台通过一种算法（哈希函数）计算出位置，然后带你过去。
• 特点：多了一个环节。虽然平均也是 $O(1)$，但那个“计算过程”和“处理冲突过程”非常耗时。

---

二、 核心区别对比表

特性	数组 (Array)	哈希表 (std::unordered_map)
访问速度	极快（真正的一步到位）	较慢（有哈希计算和冲突处理的常数开销）
空间消耗	取决于数值的范围 (Value Range)	取决于元素的个数 (Element Count)
适用场景	数值较小且连续（如 $0 \le x \le 10^6$）	数值巨大或稀疏（如 $x = 10^9$）
稳定性	极高（时间恒定）	一般（遇到精心构造的恶意数据会退化为 $O(N)$）

---

三、 启发式思维：在草稿纸上分析复杂度

当你读完题，准备动笔写代码前，请先在草稿纸上写下这两行：

1. 看值域（Value Range）：题目说 $0 \le nums[i] \le 10^4$。
   • 算一下：$10^4$ 个 int 占多少内存？
   • 计算：$10000 \times 4$ 字节 $\approx 40$ KB。
   • 结论：内存极小！果断用数组。
2. 看时间（Time Limit）：如果题目给了 $0.1s$ 的超短时限。
   • 数组访问是 CPU 的一个指令。
   • 哈希表可能是几十个指令。
   • 结论：为了卡进时限，必用数组。

---

四、 NOI 竞赛中的“潜规则”

在信息学奥赛中，关于这两者的使用有几条金牌选手的经验法则：

1. “能开数组就开数组”

如果值域在 $10^7$ 以内，数组是神。它不仅快，而且不容易写出 Bug。

2. “离散化”是数组的救星

如果数字很大（比如 $10^9$），但总共只有 $10^5$ 个数，我们可以先进行离散化（把大数字映射成小排位），然后继续用数组。

3. 警惕 std::map (注意不是 unordered_map)

• std::map 的底层是红黑树，访问一次是 $O(\log N)$。
• 在 NOI 这种对时间极其敏感的地方，如果在循环里嵌套 map，非常容易喜提 TLE。

---

五、 总结读题关键词

在读题时，通过这两个关键词来决定用谁：

• 关键词 A：“数值范围/值域”
  • 看到 $10^5$、$10^6$：数组（静态分配，最稳）。
  • 看到 $10^9$、$2^{31}-1$：哈希表（或先离散化再用数组）。
• 关键词 B：“互不相同”
  • 本题提到“元素互不相同”，这保证了数值和下标可以一一对应，是使用“数值数组”做映射的前提。

教练的一句话秘籍：

“在 NOI 里，数组是你的贴身佩剑，快且准；哈希表是你的瑞士军刀，虽然功能全，但关键时刻可能会卡壳。”

---

什么是离散化？

“离散化”这个词听起来很高级，但在 NOI 竞赛中，它其实就是一个 “排队领编号” 的过程。

当你手里的数字很大（比如 $10^9$），数组放不下，但你又想享受数组那种 $O(1)$ 访问的快感时，离散化就是你的救星。

---

一、 生活化类比：马拉松选手的号码牌

想象你正在组织一场马拉松。选手的身份证号（原始数值）可能有 18 位那么长：

• 选手 A 的身份证号：1101051990...
• 选手 B 的身份证号：3201022000...
• 选手 C 的身份证号：4403012005...

如果你想给每个选手准备一个储物柜，你不可能开出 $10^{18}$ 个柜子，那地球都装不下。

离散化的做法是：

1. 把这 3 个选手的身份证号拿出来，按从小到大排个序。
2. 给最小的人发 1 号胸牌，第二小的发 2 号，第三小的发 3 号。
3. 结果：身份证号那个巨大的数字，就被缩减成了 1, 2, 3。这就叫“离散化”。

---

二、 启发式推演：在草稿纸上模拟

假设题目给的 nums2 变得非常夸张： nums2 = [1000000000, 500, 9999999] （这些数字数组存不下！）

请跟着我在草稿纸上做这三步：

第一步：排序（找出大小关系）

把数字从小到大排列： 500, 9999999, 1000000000

第二步：去重（保证每个值唯一）

如果里面有重复的数字，只保留一个。（本题已经保证互不相同，这一步可省略，但在一般 NOI 题中必须要做）。

第三步：映射（领取新编号）

我们建立一个对应的关系表：

• 500 $\rightarrow$ 编号 1
• 9999999 $\rightarrow$ 编号 2
• 1000000000 $\rightarrow$ 编号 3

现在，原来的数组就变成了： [3, 1, 2] 这个新数组里的数字最大才 3，你可以开一个 int a[5] 的数组，轻轻松松处理它们！

---

三、 为什么离散化对单调栈有用？

回到我们的“下一个更大元素”题目。如果数值很大，我们不能直接用 next_greater[1000000000]。

离散化后的处理流程：

1. 把 nums2 里的数领到新编号。
2. 用这些新编号进单调栈。
3. 由于编号的大小顺序和原数字的大小顺序是一模一样的（比如 3 > 1 对应 10亿 > 500），所有的比较逻辑（x > s.top()）完全不受影响。
4. 存答案的时候，用 next_greater[新编号] 即可。

---

四、 竞赛代码怎么实现离散化？

在 C++14 中，我们通常用“三步走”策略：

// 1. 复制一份原数组并排序
vector<int> temp = nums2;
sort(temp.begin(), temp.end());

// 2. 去重（NOI 常用套路）
temp.erase(unique(temp.begin(), temp.end()), temp.end());

// 3. 找新编号（用二分查找，速度极快）
int get_id(int val) {
    // lower_bound 返回第一个大于等于 val 的位置
    return lower_bound(temp.begin(), temp.end(), val) - temp.begin() + 1;
}

---

五、 复杂度思考过程

• 空间：从原来的“值域有多大，空间就有多大”变成了“有多少个数，空间就有多大”。哪怕值域是 $10^{18}$，只要只有 $10^5$ 个数，我们就只占 $O(N)$ 空间。
• 时间：多了排序 $O(N \log N)$ 和二分查找 $O(\log N)$ 的开销。在 $N=10^5$ 级别时，这个开销完全可以接受。

---

六、 总结读题关键词

什么时候你要在心里大喊一声“需要离散化了！”？

1. “数值很大，但个数很少”：比如 $nums[i] \le 10^9$，但 $n \le 10^5$。
2. “只关心大小关系，不关心具体数值”：比如找“下一个更大元素”、“逆序对”、“区间内有多少个数”。
3. “需要用值作为数组下标”：这是最明显的信号。

教练的一句话：

“离散化就是把巨大的、稀疏的‘身份证号’，变成紧凑的、连续的‘排队序号’，它是连接‘海量数值’与‘高效数组’的桥梁。”

---

详细解释这里的去重写法

// 2. 去重（NOI 常用套路）
temp.erase(unique(temp.begin(), temp.end()), temp.end()); 

这一行代码 temp.erase(unique(temp.begin(), temp.end()), temp.end()); 是 C++ 竞赛编程中最经典、最常用的“套路”之一，被称为 Erase-Unique 惯用法。

在离散化中，它的作用是：把排好序的数组中重复的元素删掉，只保留一份，从而得到一个纯净的“值域映射表”。

为了让你彻底理解，我们把它拆解成三个部分来“解剖”。

---

第一步：前提条件——必须先排序

unique 函数只能处理相邻的重复元素。 如果你的数组是 [3, 1, 3]，unique 发现 3 和 1 不一样，1 和 3 不一样，它就什么都不做。 所以，在使用这一行之前，必须先执行 sort(temp.begin(), temp.end());。

---

第二步：unique 到底做了什么？（伪删除）

这是最容易误解的地方：unique 并没有真正删掉元素，它只是在做“搬运工”。

想象一个具体的例子：

假设 temp = [1, 2, 2, 3, 3, 3, 5]（已排序）。

1. unique 开始扫描，发现重复的 2 和 3。
2. 它把不重复的元素往挪到前面，覆盖掉重复的部分。
3. 执行完后，数组变成了：[1, 2, 3, 5, ?, ?, ?]。
   • 前面的 1, 2, 3, 5 是我们要的。
   • 后面的 ?, ?, ? 是残留下来的垃圾数据（长度没变）。
4. 关键返回值：unique 会返回一个迭代器（指针），指向第一个“垃圾数据”的位置（即例子中第一个 ? 的位置）。

---

第三步：erase 完成“真删除”

vector::erase(first, last) 的作用是：删掉从 first 到 last 之间的所有元素。

• first：就是 unique 返回的那个指向第一个垃圾数据的指针。
• last：就是 temp.end()。

合起来看（草稿纸模拟过程）：

初始状态：
[ 1, 2, 2, 3, 3, 3, 5 ]
  ^                  ^
begin               end

1. 执行 unique 后：
[ 1, 2, 3, 5, | 3, 3, 5 ]
              ^         ^
            it(返回)   end
   (前4个是去重后的结果)

2. 执行 erase(it, end) 后：
[ 1, 2, 3, 5 ]
  ^         ^
begin      end
   (垃圾数据被彻底清理，size 变小了)

---

四、 为什么 NOI 选手一定要写这一行？

1. 空间效率：离散化时，如果原数据有 100 万个 5，去重后只占 1 个位置，极大地节省了映射表的大小。
2. 二分查找准确性：后面我们要用 lower_bound 找编号，如果表里有重复的数，找出来的编号就乱了。
3. 时间复杂度：
   • unique 是 $O(N)$ 的，它只遍历一遍。
   • erase 也是 $O(N)$ 的。
   • 配合 sort 的 $O(N \log N)$，整套去重操作非常高效。

---

五、 启发式思考：如果手写这个过程怎么写？

在草稿纸上，如果不调用 STL，你可以尝试写出这个逻辑（这也是面试或初级 OI 经常考的）：

int j = 0;
for (int i = 0; i < n; ++i) {
    if (i == 0 || a[i] != a[i-1]) {
        a[j++] = a[i]; // 只有和前一个不一样的才往“新家”搬
    }
}
// 最后的有效长度就是 j

你会发现，unique 的内部原理其实就是这个双指针移动的过程。

---

六、 总结读题关键词

当你看到以下要求时，脑子里要瞬间弹出这一行代码：

• “统计有多少个不同的数”：unique 后看 size()。
• “进行离散化预处理”：必须去重才能建立唯一映射。
• “集合运算”：求并集、交集前通常需要先去重。

教练的叮嘱：

“sort + unique + erase 是离散化的‘三剑客’。记住，unique 只是把垃圾堆到了后院，erase 才是把垃圾车叫来拉走。”