企业官网建设流程全解析

• 文档
• 教程
• 知识库

本篇是 InterviewGuide 仓库《带你快速刷完 67 道剑指 Offer》算法专栏的第 50 题解析，完整继承原题题面、返回值约定与三套可直接提交的 C++ 实现，并补充哈希表、布尔标记、原地标记三种方案的复杂度推导、正确性分析与边界讨论。读完本篇，你将掌握"数组内数字取值范围受限（0 ~ n-1）"这一类题目的通用套路：如何用哈希表快速求解、如何用vector<bool>压缩内存、以及如何借助"数值 + n 打标记"实现不占额外空间的原地判重，并能将该套路迁移到 LeetCode 448（找到所有数组中消失的数字）等相似题目上。

题目描述与返回值约定

题目来源：《何海涛. 剑指 Offer[M]. 电子工业出版社, 2012.》，本题完整题解可见 50-剑指offer.md，同时收录于 剑指offer全集.md。

在一个长度为 n 的数组里，所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复，也不知道每个数字重复几次。请找出数组中第一个重复的数字。

例如，输入长度为 7 的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是第一个重复的数字2（从左到右扫描时，下标 4 处的2是第一次遇到的重复值，下标 6 处的3虽然也重复，但出现得比2晚）。

返回描述（函数签名约定）：

• 如果数组中有重复的数字，函数返回true，否则返回false；
• 如果数组中有重复的数字，把重复的数字放到参数duplication[0]中（duplication已经初始化，可以直接赋值使用）。

函数签名统一为：

bool duplicate(int numbers[], int length, int* duplication);

需要注意两点细节：一是题目要求返回的是"第一个重复的数字"，因此一旦在遍历过程中首次发现某个值已经出现过，就可以立刻返回，无需统计完整张哈希表；二是duplication指针已由调用方初始化，直接duplication[0] = ...或*duplication = ...赋值即可。

解法一：用 unordered_map 保存已出现数字

思路最直观：遍历数组，用一个哈希表记录每个数字是否出现过。find命中说明是重复值，立即写入duplication并返回true。

bool duplicate(int numbers[], int length, int* duplication) { unordered_map<int, int> unmp; unmp.reserve(length); for (int i = 0; i < length; ++i) { if (unmp.find(numbers[i]) == unmp.end()) { unmp.insert({ numbers[i],1 }); } else { *duplication = numbers[i]; return true; } } return false; }

代码要点与复杂度：

• unmp.reserve(length)提前为length个元素预留桶位，避免哈希表在插入过程中频繁 rehash 扩容，在 n 较大时可显著减少动态扩容带来的时间开销；
• 键值对{ numbers[i], 1 }中的1只是占位计数，本题只关心"是否出现过"，并不关心出现次数，因此也可以改用unordered_set<int>进一步省去 value 部分；
• 时间上每个元素至多经历一次find与一次insert，均摊 O(1)，整体 O(n)；
• 空间上需要 O(n) 的哈希表存储，且unordered_map底层为哈希桶 + 链表节点，常数开销较大。

适用场景：对内存不敏感、追求实现简单与可读性的场合；同时它不依赖"数字都在 0 ~ n-1 范围内"这一前提条件，是泛化性最强、可迁移到任意整数数组的通用解法。

解法二：用 vector 布尔标记，降低内存复杂度

题目给出"数字都在 0 ~ n-1 范围内"的强约束，意味着我们可以用数组下标直接映射数字本身。于是不再需要存储键值对，只需一个长度为 n 的布尔数组：result[numbers[i]]为false表示该数字第一次出现，置为true；再次遇到时即为重复数字。

bool duplicate(int numbers[], int length, int* duplication) { vector<bool> result(length,false); for (int i = 0; i < length; ++i) { if (result[numbers[i]] == false) { result[numbers[i]] = true; } else { duplication[0] = numbers[i]; return true; } } return false; }

为什么用vector<bool>而非vector<char>或vector<int>？

std::vector<bool>是 C++ 标准库中一个特化的模板，底层按位压缩存储：每个元素只占 1 bit，而非通常的 1 个字节。因此 n 个标记位仅占用约 n/8 字节，相比vector<int>（4n 字节）内存占用下降约 32 倍，相比vector<char>（n 字节）也下降 8 倍。这正是原文档中"减少内存、降低内存复杂度"的核心手段。

需要留意的一点是：由于按位压缩，vector<bool>::reference不是真正的bool&，在需要取地址或进行某些泛型操作时会有行为差异；但在本题"只做赋值与读取比较"的场景下完全安全。

复杂度：时间 O(n)，空间 O(n/8)（位压缩），且没有哈希表节点分配的开销，实际常数远小于unordered_map方案。原文档记录阿秀在牛客网二刷该写法时的提交数据为运行时间 2ms、占用内存 508k。

解法三：原地标记法——不占用任何额外空间

解法二虽然把内存压到了 n/8 字节，但依然"占用"了额外空间。题目中"所有数字都在 0 ~ n-1 之间"这一条件还有一个更极致的用法：复用输入数组本身来打标记。

核心思想：当一个数字index被访问过后，就让numbers[index]加上n作为"已访问"标记。由于每个数字的取值范围都在0 ~ n-1，原始值加上 n 后必然>= n，于是"numbers[index] >= length"就可以作为该下标已被访问过的判定依据；再次遇到相同数字时，便能立刻发现并返回。

bool duplicate(int numbers[], int length, int* duplication) { for (int i = 0; i < length; ++i) { int index = numbers[i]; if (index >= length) index -= length; if (numbers[index] >= length) { duplication[0] = index; return true; } numbers[index] += length; } return false; }

逐行推演正确性（以输入{2, 3, 1, 0, 2, 5, 3}，n = 7 为例）：

可以看到，第 4 轮扫描到第二个2时，numbers[2]已被第一轮加过 n，值 >= 7，于是立刻判定2重复。"第一个重复的数字"语义也由此得到保证——我们始终是从左到右扫描、首次命中即返回。

为什么需要if (index >= length) index -= length;？

因为当前元素numbers[i]本身也可能是之前某轮被加过 n 的"标记值"。例如轮次 i 取到numbers[i] = 8时，它真实代表的是数字8 - 7 = 1，所以必须先把index还原到[0, n-1)范围内，再用它作为下标去查/打标记。这一行是整个算法正确性的关键，也是容易被忽略的坑。

复杂度：时间 O(n)，空间 O(1)（完全复用输入数组）。原文档记录阿秀在牛客网二刷该写法的提交数据为运行时间 2ms、占用内存 476k，与布尔标记方案接近。

适用前提与限制：

• 必须以"可以在输入数组上做修改"为前提——牛客网本题的输入numbers[]允许原地修改，因此该方案可直接提交；
• 若面试官限定"不能修改原数组"，则需退回解法二，或改用"下标映射 + 抽屉原理（鸽巢原理）二分"等不修改数组的判定方案；
• 因为每个位置的原始值在加法后变成[n, 2n)区间，两次及以上重复访问都能被>= n正确识别，标记是幂等累积的，不需要回滚。

二刷版本：更简洁的原地标记写法

阿秀二刷时对原地做法做了简化——用取模运算index = numbers[i] % length一步完成"还原"与"取下标"，其余逻辑不变：

bool duplicate(int numbers[], int length, int* duplication) { for(int i = 0;i < length; ++i){//这个方法妙在对于依次遍历过的每个数，都能在数组里记忆它出现过了。 //比如{2,2,1,0}，第一次循环index = 2,a[2]=a[2] + 4 = 5,这样，a[2]=5 > 数组长度4,就说明2这个数字出现过了。 int index = numbers[i]%length; if( numbers[index] >= length){ duplication[0] = index; return true; } numbers[index] += length; } return false; }

两种原地写法的等价性：

• 初版写法：index = numbers[i]，若index >= length则index -= length；
• 二刷写法：index = numbers[i] % length。

由于numbers[i]的取值只有两种可能——原始值v ∈ [0, n)，或被打过标记的v + n ∈ [n, 2n)——前者对 n 取模仍是v，后者(v + n) % n也恰好还原为v。因此% length与"判断再减"在数学上完全等价，且写法更紧凑、无需分支。原文档中阿秀的注释以{2,2,1,0}为例：第一次循环index = 2，a[2] = a[2] + 4 = 5 > 4，说明2出现过，逻辑一目了然。

三种解法对比与选型建议

面试与笔试的选型建议：先给面试官讲清楚题意与"数字范围受限"这一关键突破口，然后按"哈希表 → 布尔数组 → 原地标记"的递进顺序给出三种方案，并主动说明各自的时空复杂度与是否修改原数组——这本身就是一次完整的"由通用到特化、由简单到极致"的复杂度优化演示。笔试提交时，牛客网本题下原地标记写法与vector<bool>写法实测（原文档记录）均在 2ms 左右，内存 476k~508k，差别不大，优先选择自己最有把握、不会写错的版本。

延伸思考：与 LeetCode 448 及一类"标记题"的关系

原文档特别指出，本题原地做法与 LeetCode 448《找到所有数组中消失的数字》很像，做法差不多。两者的共同点在于：

• 数组长度都为 n，元素取值范围都在[1, n]或[0, n-1]；
• 都可以用"以值为下标"的思路把数组本身当作哈希表使用；
• 都可以通过"给对应下标的元素加 n（或取负）"来做访问标记。

区别只在于：448 要求找出所有未出现的数字（需要遍历两次，第二次收集标记值 < n 的下标），而本题只需找出第一个重复的数字（遇到已标记下标即返回）。掌握"值域受限 + 原数组打标记"这一范式，即可同时覆盖这两类高频题。

仓库中与之呼应的内容还包括：算法模块的整体食用指南（含校招/社招不同人群的刷题路径建议）见 01-basic-algorithm/01-introduce.md；本专栏共 67 题、题目顺序与牛客网剑指 Offer 专题保持一致，专栏说明见 02-sword-offer/01-introduce.md；力扣精选刷题笔记见 03-leetcode/01-introduce.md。若时间紧张、想优先突击面试高频题，可参考 04-high_frquency_algorithm/01-high_frquency_algorithm.md。

补充一道自查边界题：输入{0, 1, 2, 3}（无重复）时，三种解法都应返回false且不写duplication；输入{0, 0}时，原地标记法在第 2 轮发现numbers[0] >= 2，正确返回0。建议在本地编译器（如 g++，需包含<unordered_map>与<vector>头文件并using namespace std;）中跑通这三段代码，再进入牛客网对应题号提交验证。

• 文档
• 教程
• 知识库