题目

请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为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;
    }
        
}