12 判断数组中是否有重复值（堆排序）

请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。

给定一个int数组A及它的大小n，请返回它是否有重复值。

测试样例：[1,2,3,4,5,5,6],7

返回：true

思路：非递归的堆排序

import java.util.*;

public class Checker {
         public boolean checkDuplicate(int[] a, int n) {
        for(int i=n-1;i>=0;i--){
          heap_sort(a, n--);
           int temp=a[i];
              a[i]=a[0];
              a[0]=temp;
        }
        int num=a[0];
        for(int i=1;i<a.length;i++){
          if(a[i]==num){
            return true;
          }else{
            num=a[i];
          }
        }
        return false;
      }
      //非递归的堆调整
      public void heap_sort(int[] A,int n){
        int leftChild;
        int rightChild;
        int max;
        int i;
        for(int j=n/2-1;j>=0;j--){
          i=j;        
          while(i<n/2){
            max=i;
            leftChild=i*2+1;
            rightChild=i*2+2;
            if(leftChild<n&&A[leftChild]>A[max]){
              max=leftChild;
            }
            if(rightChild<n&&A[rightChild]>A[max]){
              max=rightChild;
            }
            if(max!=i){
               int temp=A[max];
                  A[max]=A[i];
                  A[i]=temp;

                  i=max;
            }else{
              break;
            }
          }
        }        
      }
}