前言

数组是一种最基本的数据结构，它占据一块连续的内存，并按照顺序存储的方式存储数据。
为了解决数组空间效率不高的问题，动态数组出现了，典型的代表是 vector。思想是先为动态数组预先分配一块内存空间，等到数组容量不足时重新开辟一块内存空间，并复制原数组到新空间，最后释放旧内存空间。对于Vector 来说，每次扩容为之前的 2 倍。由于该操作对时间性能影响较大，因此使用动态数组应该尽量避免改变数组容量大小的次数。

数组和指针的区别

数组和指针的区别

• 使用指针访问数组中的元素时，需要确保不越界；
• 对数组求 sizeof ，还需要考虑元素所占的字节，比如在 32 位的机器上，每个整数占4字节，那么例子中 data1 就是 5*4=20；
• 在 32 位系统上，对任意类型的指针求 sizeof 得到的结果都是 4；
• 当数组作为函数的参数进行传递时，自动退化为指针，因此求 sizeof 结果同上条。

题目描述(数组中重复的数字)

题目一(找出数组中重复的数字)

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

解题思路

1. 排序。对数组排序后，依次比较前后元素是否重复即可。但时间复杂度为O(nlogn),空间复杂度为 O(1)。
2. 利用哈希表。利用键值对映射，可以将数组中的元素依次插入插入哈希表中，但是插入之前需要判断是否已存在该值，如果存在则说明该位置的元素重复了，算法的缺点是空间复杂度为 O(n)。
3. 下标定位法。

接下来详细介绍下下标定位法。
注意到题目中数字的范围都在 0-n-1 范围内，假如不存在重复的元素，那么对数组进行重新排序后，数组的索引 i 一定可以对应到单个数字i,否则数字i存在多个。

我们先依次遍历数组中的每个元素，当扫描到索引为 i 的数字 m 时，先比较数字 m 是否等于 i，如果等于则接着扫描下一个数组元素；如果不等，则将数字 m 和数组中索引为 m 的数字 n 进行比较，如果重复(m=n)，则找到了一个重复的数字；如果不重复(m!=n)，那么交换 m 与 n。交换后，此时索引 i 上的数字 m 再和索引 i 进行下一轮的比较，重复上面的步骤，直至数字 m 与索引 i 相同。那么我们就在这个比较交换的过程中寻找重复的元素。

算法实现

算法实现

复杂度分析

代码中虽有两次循环，但每个数字最多只要交换两次就能找到属于它子集的位置，因此总的时间复杂度为 O(n)。另外，所有操作都在原数组上进行，所以空间复杂度为 O(1)。

题目二 (不修改数组找出重复的元素)

在一个长度为 n+1 的数组里的所有数字都在 1-n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组 {2,3,5,4,3,2,6,7},
那么对应的输出是重复的数字 2 或者 3。

解题思路

1. 辅助数组法。依然是按一个下标对应一个数字的思路，先构建一个长度为 n+1 的数组，然后将原数组中的元素依次插入到辅助数组中相应的下标位置上。这样就能发现那个数字重复了。方法的缺点就是空间复杂度为 O(n)。
2. 二分查找法。若 1-n 的范围里只有 n 个数字则一定不会重复，否则必定存在重复的元素。那现在我们把 1-n 的数字从中间的数字 m 分为两部分，那么前一半为 1-m，后一半为 m+1-n，假如前半部分中介于 1-m 中的数字个数超过了 m，那么这一半的区间必定存在重复的元素。接下来可以继续在这一半空间的二分查找，直至找到重复的元素。

算法实现

算法实现

复杂度分析

算法中使用二分查找的思想，复杂度 O(logn),在计数的时候使用了一个循环复杂度为 O(n),因此，总的时间复杂度为 O(nlogn),操作在原数组上进行，时间复杂度为 O(1)。

参考

<<剑指offer第二版>>