题目
请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。
给定一个int数组A及它的大小n，请返回它是否有重复值。
测试样例：[1,2,3,4,5,5,6],7
返回：true
思路
如果没有空间复杂度的限制，我们应该用哈希的思想去做。但是本题要求空间复杂度必须为O(1)。所以我们先进行排序，再比较相邻的元素是否重复即可。所以我们需要一种空间复杂度为O(1)的排序算法，非递归的快速排序和堆排序都是时间复杂度O(n*lgn)，空间复杂度O(1)的。这里我们选用堆排序，代码如下。
import java.util.*;
public class Checker {
public boolean checkDuplicate(int[] a, int n) {
heapSort(a);
for(int i=0;i<n-1;i++){
if(a[i]==a[i+1]){
return true;
}
}
return false;
}
private void heapSort(int []a){
int hi=a.length-1;
//建堆
for(int i=(hi-1)/2;i>=0;i--){
sink(a,i,hi);
}
//下沉排序
for(int i=hi;i>=0;i--){
swap(a,0,i);
sink(a,0,i-1);
}
}
private void sink(int[]a,int lo,int hi){
int child;
while((child=lo*2+1)<=hi){
if(child<hi&&a[child]<a[child+1])child++;
if(a[lo]>=a[child]) break;
swap(a,lo,child);
lo=child;
}
}
private void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
