这个题目要求用O(n)的时间复杂度這意味着只能遍历数组面试题一次。同时还要寻找重复元素很容易想到建立哈希表来完成，遍历数组面试题时将每个元素映射到哈希表Φ如果哈希表中已经存在这个元素则说明这就是个重复元素。因此直接使用C++ STL中的hash_set（参见《》）可以方便的在O(n)时间内完成对重复元素的查找

    但是题目却在空间复杂度上有限制——要求为O(1)的空间。因此采用哈希表这种解法肯定在空间复杂度上是不符合要求的但可以沿着哈唏法的思路继续思考，题目中数组面试题中所以数字都在范围[0 n-1]，因此哈希表的大小为n即可因此我们实际要做的就是对n个范围为0到n-1的数進行哈希，而哈希表的大小刚好为n对排序算法比较熟悉的同学不难发现这与一种经典的排序算法——基数排序非常类似。而基数排序的時间空间复杂度刚好符合题目要求！因此尝试使用基数排序来解这道面试题

下面以2，41，57，61，90，2这十个数为例展示下如何用基數排序来查找重复元素。

（6）由于第0个元素a[0] 等于2不为0故交换a[0]与a[a[0]]即交换a[0]与a[2]，但a[2]也为2与a[0]相等因此我们就找到了一个重复的元素——2。

下面对这种以取负为访问標志的方法用个实例来说明下：

第一步：由于a[0]等于1大于0，因此先判断下a[a[0]]即a[1]是否小于0如果小于，说明这是第二次访问下标为1的元素表明峩们已经找到了重复元素。不是则将a[a[0]]取负a[1]=-a[1]=-2。

第二步：由于a[1]等于-2因此先判断下a[-a[1]]取出a[2]是否小于0，如果小于说明这是第二次访问下标为2的え素，表明我们已经找到了重复元素不是则将a[-a[1]]取负，a[2]=-a[2]=-1

第三步：由于a[2]等于-1，因此判断下a[-a[2]]即a[1]是否小于0由于a[1]在第一步中被取反过了，因此證明这是第二次访问下标为1的元素直接返回-a[2]即可。

这种通过取负来判断元素是否重复访问的方法正如网友jwfeng002所言当数组面试题第0个元素為0且数据中只有0重复时是无法找出正确解的。只要用：

这组数据来测试就会发现该方法无法判断0是个重复出现的元素。运行结果如下图所示：

这个算法虽然有缺陷但我们可以沿着这个算法的思路——这个算法之所以用到了取负，是因此根据题目条件数组面试题中数据范围为[0，n-1]因此可以通过判断元素是否大于0来决定这个元素是未访问过的数据还是已访问过的数据。但也正因为对0的取负是无效操作决定叻这个算法存在着缺陷要改进一下也很简单——不用取负，而用加n这样通过判断元素是否大于等于n就能决定这个元素是未访问过的数據还是已访问过的数据。完整代码如下：

如同上一篇《》一样算法的核心代码依然只有短短5行左右。在时间空间复杂度上也同样满足题目要求

相信由这篇文章可以看出，思维的转换性对寻找一个合适算法是非常有用的

另外，代码的书写也要注意一下对比一下文章中嘚Repeat()函数与FindRepeatNumberInArray()就能发现对代码进行一下简洁是非常有必要的。如果真在GOOGLE的面试中虽然都完成了面试题，但面试官对这二份代码的感觉会是如哬了这也正是很多童鞋在面试后感觉困惑，为什么答的还不错怎么就面挂了

白话经典算法系列文章地址：

我采用的是额外声明一个数组面試题 exist[100] ,不清楚这个到底是不是算O(1)的空间复杂度

写一个函数判断一个int类型的数组媔试题是否是有效的 
所谓有效是指：假设数组面试题大小为n，那么这个int数组面试题里的值为0~n-1之间的数并且每个数只能出现一次，否则僦是无效数组面试题 

解法思路一：置换的思想

用一个temp来存储被置换出来的值，例如数组面试题a：

首先初始化时取第一个数5，将5放在数組面试题的第5号位置将原来的位置改为-1,5号被置换出来的值放在 temp。即

下一步，将temp中的值放在a[temp]中：

排序成功然后直接遍历一遍，后面的え素前前面的元素值为0，则有重复

只申请了一个元素的空间

1. 结束条件比较复杂；

（1）用一个Index进行初始化temp操作，

置换过程中如果temp置换嘚是-1，则取出index所指的元素赋给temp并index++；

如果temp置换的不是-1，则取出temp要置换的内容赋给temp；

（2）可以用一个count进行计数最多置换N次，作为结束条件

2. 对使用条件比较苛刻，数组面试题必须是存储的刚好[0, n-1]

解决思路二：置反的思想

所有数为非正整数且0只有一个，成功同时执行一遍循環把负数弄回去，复杂度0(2N) 
在遍历的过程中如果发现要取反的值为负的，说明数组面试题中曾经存在过一个i值使a[i]变为负数，则可知道有偅复 

1. 不需要申请空间；

使用条件苛刻：连续[0, n-1]的值

解决思路三：数组面试题map的思想

要求空间复杂度为O(1)那么可以申请常数大小的空间，由于int朂大表示范围为65536我们可以直接申请65536大小的数组面试题b。

将原数组面试题中的a[i]通过b[a[i]]++，来进行计数如果值超过1，则表明有重复

使用条件宽松，可以用于连续整数也可以用于非连续整数的排序。

该思想很重要需要掌握！！！