怎么判断一个整数数组中是否有重复元素？要求时间复杂度O(n)，空间复杂度O(1)
题目：
写一个函数判断一个int类型的数组是否是有效的。
所谓有效是指：假设数组大小为n，那么这个int数组里的值为0~n-1之间的数，并且每个数只能出现一次，否则就是无效数组。
例如[5,3,1,4,2,0]是有效的,[5,3,5,1,2,0]是无效的,[5,3,6,1,2,0]是无效的。
解法思路一：置换的思想
用一个temp来存储被置换出来的值，例如数组a：
5 3 1 4 2 0
首先，初始化时取第一个数5，将5放在数组的第5号位置，将原来的位置改为-1,5号被置换出来的值放在 temp。即，
-1 3 1 4 2 5 temp=0
下一步，将temp中的值放在a[temp]中：
0 3 1 4 2 5
接着，置换3：
0 -1 1 3 2 5 temp=4
0 -1 1 3 4 5 temp=2
0 -1 2 3 4 5 temp=1
0 1 2 3 4 5
排序成功，然后直接遍历一遍，后面的元素前前面的元素，值为0，则有重复。
优点：
只申请了一个元素的空间
缺点：
1. 结束条件比较复杂；
2. 对使用条件比较苛刻，数组必须是存储的刚好[0, n-1]
解决思路二：置反的思想
不用移动的方法
5 3 1 4 2 0
==》0） 5 3 1 4 2 -0 i=0; 取出j=|a[i]|=5; 令a[j]=-a[5]=-0
1） 5 3 1 -4 2 0 i=1; 取出j=|a[i]|=3; 令a[j]=-a[3]=-4
2） 5 -3 1 -4 2 0 i=2; j=|a[i]|=1; 令a[1]=-a[1]=-3
3） 5 -3 1 -4 -2 0 i=3; j=|a[i]|=4; 令a[4]=-a[4]=-2
4） 5 -3 -1 -4 -2 0 i=4; j=|a[i]|=2; 令a[2]=-a[2]=-1
5） -5 -3 -1 -4 -2 0 i=5; j=|a[5]|=0; 令a[0]=-a[0]=-5
所有数为非正整数，且0只有一个，成功。同时执行一遍循环把负数弄回去，复杂度0(2N)
在遍历的过程中，如果发现要取反的值为负的，说明数组中曾经存在过一个i值，使a[i]变为负数，则可知道有重复
优点：
1. 不需要申请空间；
缺点：
使用条件苛刻：连续[0, n-1]的值
解决思路三：数组map的思想
要求空间复杂度为O(1)，那么可以申请常数大小的空间，由于int最大表示范围为65536，我们可以直接申请65536大小的数组b。
将原数组中的a[i]，通过b[a[i]]++，来进行计数，如果值超过1，则表明有重复。
优点：
申请空间比较大
缺点：
使用条件宽松，可以用于连续整数，也可以用于非连续整数的排序。
该思想很重要，需要掌握！！！
【注】以上部分思想来源于 北邮人。
- 3楼chongoudaxia10分钟前
- 好算法
- Re: yahohi10分钟前
- 回复chongoudaxian呵呵，共同学习
- 2楼liulin063326昨天 23:57
- 提出一种新的解决方法，此方法之前浏览帖子看过，感觉也可解次问题。n其主要思路是两个数进行异或，弱同一个数异或两次，则原数不变，因此可先对0----n进行异或得到结果，然后利用此结果对a[0]...a[n-1]进行异或，如果为原始数据，则表示0---n-1在此数组中出现且仅出现一次。n代码如下：nbool containRepeatNumber(int arr[], int n){ntint start = -1;ntfor(int i=0; i<n;i++){nttstart ^=i;nt}ntfor(int i=0; i<n; i++){nttstart = start^arr[i];nt}ntreturn -1 == start;n}
- 1楼liulin063326昨天 19:07
- 第二个 for循环是nfor(int i=0; i<n; i++){nstart ^=arr[i];n}n少打了个arr[i]，不好意思
- Re: yahohi昨天 23:55
- 回复liulin063326n异或的思路是有问题的，比如：n0,1,2,3异或结果为1；n0,0,0,1的异或结果也为1.