题目中并没有交代该数组是有序嘚还是无序的所以需要考虑无序和有序两种情况。 第一种情况数组是有序的，这个当然比较简单了只需要两个下标就可以解决问题，直接上代码如下： public class Algorithm { ...

写一个函数判断一个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，则表明有重复

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

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