笔者最近在找工作时，无意间读到了一本名为《剑指offer》的书，粗略翻阅了一下，感觉这将会是一本能让我不再苦恼于笔试和面试“手搓代码”的书。故笔者写下该系列博客记录自己的学习历程，希望能和这本书的读者朋友们一起交流学习心得。
介绍：《剑指Offer：名企面试官精讲典型编程题（第2版）》剖析了80个典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这5个面试要点。
编程题链接：牛客网在线编程_算法面试_面试必刷TOP101 (nowcoder.com)
本博客关键词：数组中重复的数
题设：
链接：数组中重复的数字_牛客题霸_牛客网 (nowcoder.com)
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1。
测试用例
- 长度为n的数组包含一个或多个重复的数字：
{2, 3, 1, 0, 2, 5, 3} - 数组中不包含重复的数字：
{2, 3, 4, 5, 6, 7, 1, 0} - 无效输入：
{9, 6, 4, 11}{-2, 10001}{}
方法一：先排序后遍历
比较简单的一个方法：
- 时间复杂度：受排序函数影响，假如是快排，则平均时间复杂度是
O(nlogn) - 空间复杂度：受排序函数影响，假如是快排，则最好为
O(nlogn)
int duplicate(vector<int>& numbers) {//if (numbers.size() <= 0 || numbers.size() > 10000) {if (numbers.size() <= 0) {return -1;}for (auto num : numbers) {if (num > numbers.size() - 1 || num < 0) {return -1;}}// 法一：排序后扫描sort(numbers.begin(), numbers.end());for (int i = 0; i < numbers.size() - 1; i++) {if (numbers[i] == numbers[i + 1]) {return numbers[i];}}return 0;}
我首次编译时这个解法卡在了第九个测试用例里，问题出现在numbers.size() > 10000里，因为按照题目要求，数组长度n的范围是在0~10000之间的，可是测试用例9的numbers.size()居然是10002，感觉这个测试用例是不对的，不过问题不大不影响做题~
方法二：哈希表
这个方法也比较简单，前提是掌握哈希表相关函数的性质。
- 时间复杂度：
O(n)，每个元素在哈希表中查找和插入的时间复杂度都是O(1)，遍历整个数组需要O(n)。 - 空间复杂度：
O(n)，在最坏的情况下，所有元素都不重复，哈希集合需要存储 n个元素。
int duplicate(vector<int>& numbers) {// if (numbers.size() <= 0 || numbers.size() > 10000) {if (numbers.size() <= 0) {return -1;}for (auto num : numbers) {if (num > numbers.size() - 1 || num < 0) {return -1;}}// 法二：哈希表unordered_set<int> set;for (auto num : numbers) {if (set.find(num) != set.end()) {return num;}set.insert(num);}return 0;}
方法三：
这是一个比较巧妙的方法：
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
int duplicate(vector<int>& numbers) {// if (numbers.size() <= 0 || numbers.size() > 10000) {if (numbers.size() <= 0) {return -1;}for (auto num : numbers) {if (num > numbers.size() - 1 || num < 0) {return -1;}}// 法三：数组重排for (int i = 0; i < numbers.size(); i++) {while (numbers[i] != i) {if (numbers[i] == numbers[numbers[i]]) {return numbers[i];}swap(numbers[i], numbers[numbers[i]]);}}return 0;}
这个方法的主要思路就是：数组的元素的值要放在对应的位置上，比如数组某个元素的值为5，则就将这个值与索引5位置上的值交换，如果这个值刚好与索引5位置上的值相等，则表示出现了重复的元素。