題目

請設(shè)計一個高效算法，判斷數(shù)組中是否有重復(fù)值。必須保證額外空間復(fù)雜度為O(1)。
給定一個int數(shù)組A及它的大小n，請返回它是否有重復(fù)值。

測試樣例：[1,2,3,4,5,5,6],7
返回：true

思路

如果沒有空間復(fù)雜度的限制，我們應(yīng)該用哈希的思想去做。但是本題要求空間復(fù)雜度必須為O(1)。所以我們先進行排序，再比較相鄰的元素是否重復(fù)即可。所以我們需要一種空間復(fù)雜度為O(1)的排序算法，非遞歸的快速排序和堆排序都是時間復(fù)雜度O(n*lgn)，空間復(fù)雜度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;
    }
        
}