找出数组中重复的数字。
相关题目：剑指Offer面试题3: 数组中重复的数字。
问题1: 数组中元素的取值范围是多少？数组的长度？
问题2: 数组是否可以修改？
问题3: 数组中重复元素有多少？找出多少重复元素？
问题4: 异常情况怎么处理，如数组为null，数组长度小于2，数组中不包含重复元素，如果数组元素取值范围是0～n-1但是数组中包含大于n-1的元素，这些情况应该怎么处理。
算法1: 排序+遍历
如果数组可以修改，并且元素的取值范围比较大，例如：从Integer.MIN_VALUE到Integer.MAX_VALUE。那最简单的算法就是将数组排序，重复的元素就会被放到一起，然后遍历数组找到重复元素。
时间复杂度：O(nlogn)
空间复杂度：O(1)
算法2: 每次将一个数字交换到相应位置
如果题目中给出附加条件：数组中元素的取值范围是0～n-1。那么我们可以利用这个条件对该算法做进一步优化。
由于数组中元素取值范围是0～n-1，那么将数组排好序以后，每个元素的值应该和其下标相等。利用这个性质，我们在遍历数组的过程中，每次将一个数交换到正确位置，如果在交换过程中发现重复元素，则返回。
时间复杂度：O(n)
空间复杂度：O(1)
算法3: 每次将一个位置标记为负数
在算法2中我们每次将一个元素交换到指定位置，但是当前指针下就右会出现一个新的数字，我们需要继续将这个新的数字交换到指定位置，指针不能向前移动，这种情况下算法2的时间复杂度实际上比O(n)要大，我们可以对算法2做进一步优化，使其最坏情况下的时间复杂度降到O(n)。
对于每一个数字，我们知道它的最终位置在哪，我们并不将这个数字交换到指定的位置，而是在指定位置做一个标记，说明这个数字我们已经访问过了，我们做的标记，就是将指定位置的数字变为负数，下次如果我么右来到这个位置，看到该位置的数字为负数的时候，我们就找到了一个重复数字。这样对于每个元素，仅需要遍历一次我们就可以知道它是不是重复元素，相较于算法2，时间性能又大幅提升了。
时间复杂度：O(n)
空间复杂度：O(1)
这个算法的例子见：Leetcode442. Find All Duplicates in an Array
算法4: Hash数组统计元素是否出现
如果数组不可以修改，我们可以使用HashMap统计元素是否出现，然后遍历HashMap找出重复数字。
时间复杂度：O(n)
空间复杂度：O(n)
由于HashMap只是统计元素是否出现，我们完全可以使用一个boolean数组代替HashMap来降低一些空间复杂度。我们可以先找出数组中最大数max和最小数min来确定boolean数组的长度len = max - min + 1，然后每次从原数组中取出一个元素m，将boolean[m - min]置为true，如果发现该位置已经为true，那说明该元素就是重复元素。
时间复杂度：O(n)
空间复杂度：O(n)
我们继续优化算法来避免O(n)的空间复杂度。
算法5: 二分统计
如果数组不可以修改，并且数组中元素的取值范围是0～n-1。
和算法4类似，该算法也需要统计元素出现的次数，但不同的是，这次我们基于分治法的思想，统计一个区间内元素出现的次数，从而降低时间复杂度。
由于已知数组中元素的取值范围在0～n-1之间，我们可以将这个区间分为0～n/2-1和n/2～n-1两个区间，分别统计数组中在这两个区间内的元素出现的次数，如果一个区间内元素出现的次数超过了区间的长度，那说明该区间内肯定存在重复元素，接下来，我们再将这个区间一分为二，统计元素出现的次数，直到找到重复元素为止。
时间复杂度：O(nlogn)
空间复杂度：O(1)
和算法4相比该算法相当于用时间换空间。
需要指出的是：**该算法不一定每次都能找到重复数字！**例如对于数组[2,2,3,4,5,6]，在1～3范围内元素出现的次数是3次，在4～6范围内元素出现的次数也是3次，算法找不到重复数字。
算法6: 将数组映射为有环链表
如果数组中的元素取值范围是0～n-1。
那么我们就可以将数组映射为一个有环链表，用链表中判断环入口节点的算法就可以找到重复元素。
映射规则：以元素下标作为node.val，以元素值作为node.next。当两个node.next值相同时链表中就会产生环。
时间复杂度：O(n)
空间复杂度：O(1)
这个算法有个很明显的问题：如果一个元素的值和其下标相同时，映射为节点时相当于节点的next指针指向该节点本身，链表就断了。
如果题目可以去掉数组不可修改(read-only)这个条件，这个问题就很容易解决，我们只需要遍历数组，将元素值和其下标相等的元素和相邻元素对换，直到数组中每个元素的值都不等于其下标为止。
总结
- 如果数组中元素的取值范围很大，那么我们只能使用排序+遍历和HashMap统计次数这两种算法。
- 如果数组中元素的取值范围在数组长度范围内，我们就可以分别对排序+遍历算法和HashMap算法进行优化，优化过后的排序+遍历算法性能最好，达到O(n)的时间复杂度。并且还可以用二分统计和有环链表算法。
- 如果题目中又给出read-only条件，那么排序+遍历算法就不能用了，可以使用的算法只有二分统计和HashMap统计，由于二分统计存在缺陷，所以最优的算法只有Hash数组统计了。