求数组中重复的数字？
代码语言：javascript复制public static void main(String[] args) {
int[] data = {2, 3, 1, 0, 2, 5};
Main main = new Main();
main.isDuplicate(data);
}
public void isDuplicate(int[] arg){
HashSet<Integer> set = new HashSet<>();
for (int a: arg) {
if (set.contains(a)) {
System.out.println(a);
} else {
set.add(a);
}
}
}首先我们想到的就是hash,通过hash判断一个数字是否在之前出现过只需要O(1)的时间复杂度，我们知道hashset的底层过就是hashmap的key，即hash的实现。
但是当数据散乱的程度非常大时，hash会非常消耗空间复杂度。比如数列0,1963,2，15，同时也可能会产生hash的冲突时间。
因为其是数字，同时其数列中的数字只出现在0-n-1所有，我们可以采用直接定址法，这样避免了hash的冲突时间，也同时可以减少空间的复杂度。
代码语言：javascript复制 public static void main(String[] args) {
int[] data = {2, 3, 1, 0, 2, 5};
Main main = new Main();
main.isDuplicate(data);
}
public void isDuplicate(int[] data){
int len = data.length;
int[] array = new int[len 1];
for (int i = 0;i < len;i ){
if(array[data[i] 1]==0) {
array[data[i] 1] = data[i] 1;
}else if(array[data[i] 1]==data[i] 1){
System.out.println(data[i]);
}
}
}但是即使这样空间的复杂度也是O(n),如果要使用O(1)的复杂度，即本地进行比较的话应该怎么办？
可以本地使用快排的交换思想，快速将数据的位置定位，同时我们规定， nums[i] == i，当前位置的数据应该等于当前位置的坐标。 这样就可以使用O(1)的空间负责度完成去重定位。
代码语言：javascript复制public static void main(String[] args) {
int[] data = {2, 3, 1, 0, 2, 5};
Main main = new Main();
int[] duplication = new int[6] ;
main.isDuplicate(data,6,duplication);
System.out.println(duplication[0]);
}
public boolean isDuplicate(int[] data,int length,int[] duplication) {
if (data == null || length <= 0)
return false;
for(int i = 0; i < length; i ){
while(data[i]!=i){
if(data[i]==data[data[i]]){
duplication[0] = data[i];
return true;
}
swap(data,i,data[i]);
}
}
return false;
}
private void swap(int[] data, int i, int j) {
int a = data[i];
data[i] = data[j];
data[j] = a;
}
