前言

这次没什么说的，干就完了

一 题目

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或3.

二 思路

作者提到解决此类问题有两大思路：

排序。排完序，什么魑魅魍魉都可以看到。哈希表。每扫描到一个数字就把它装到对应的哈希表里面，如果发现，表中已经有了该数字，就说明该数字重复了。时间复杂度为$O(n)$，空间复杂度为$O(n)$

2.1 基本思想

解决该问题，使用的基本思想是排序，但是如果是一般的排好序再一个个的比对未免也太复杂了，在这里，可以利用数组的一个规律，在排序的过程中，把重复的项给找了。

一维数组在内存中占据连续的空间，因此我们可以根据下标定位对应的元素

我们注意到数组中的数字都在0~n-1的范围内。如果这个数组中没有重复的数字，那么当数组排序之后数字i将出现在下标为i的位置。由于数组中有重复的数字，有些数字除了在它自己下标所在位置外，还可能占了其他下标的位置，同时有些位置可能没有数字。

从头到尾扫尾整个数组a[]；如果扫描到下标为i的数字时，判断这个数字a[i]是否等于i。若a[i]=i，转1继续扫描下一个元素；若a[i] != i，则转3。现在已知a[i] != i，再判断a[ a[i] ]是否和a[i]相等的，如果相等，则说明，这个数字是重复的了，直接赋值输出。如果a[ a[i] ] ！= a[i]，则将a[ a[i] ]的内容和a[i]内容互换。如此循环，得到最后的重复数字。

至于怎么理解上面的算法，是观察数组的数的规律得出的：

01234562310253132025331202530123253

第一行为下标，第二行为数组中各项元素，第三到最后一行就是整个程序执行的过程，跟着走一遍，就能理解算法的精髓。

妙啊~！

2.2 实现

bool duplicate( int numbers[], int length, int * duplication ) { // 边界条件： 1. 数组不为空、长度大于0； 2. 数组元素大小在0~n-1 if ( (numbers == nullptr) || (length <= 0) ) { return false; } for (int i = 0; i < length; i++) { if ( (numbers[i] < 0) || (numbers[i] > length-1) ) return false; } // 主功能函数 for (i = 0; i < length; i++) //从头开始扫描整个数组 { while (numbers[i] != i) //数组下标是否等于数组元素 {// 若不等 if ( numbers[i] == numbers[ numbers[i] ] ) // 判断是否为重复数字 { *duplication = numbers[i]; return true; } // 如果不为重复数字，则交换数字numbers[i]至其对应下标 int temp = numbers[i]; numbers[i] = numbers[temp]; numbers[temp] = temp; }// end while }// end for return false; //没有重复 }

2.3 性能分析

时间复杂度：$O(n)$ 别看有一个for和一个while，实际上每个元素至多交换两次位置，因此时间复杂度为$O(n)$

空间复杂度：$O(1)$

2.4 测试集

长度为n的数组里包含至多一个或多个重复数字数组中不包含重复数字无效输入（空指针；数组元素存在不在0-n-1之间的数字）

三 收获

数组的最显著的特点：它是一组连续地址的存储空间。我们可以利用它干好多事。这里干的是利用它的下标和元素对应关系不会做？拿着数据去找规律吧。

参考文献

[1] 何海涛著.剑指OFFER 名企面试官精讲典型编程题 第2版[M].北京：电子工业出版社.2017.