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

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

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

返回：true

 

因为这道题对空间复杂度有要求，所以想用非递归堆排序。

 

#include 
      
       #include 
       
        #include "string.h"#include "stdio.h"#include 
        
         #include 
         
          #include
          
           #include 
           
            using namespace std;class Sort {public: int *data; int count;//堆中存在的节点数 bool checkDuplicate(int* a, int n) { data = new int[n+1]; for(int i = 0;i
            
             = 1 ; i -- )//从树种第一个不是叶子结点的索引开始 shiftDown(i); for( int i = n-1 ; i >= 0 ; i-- ) a[i] = extractMax();　　　　　//对排序后的数组做判断，是否存在重复的数字 for(int i=0;i
             
              0); int ret = data[1];//堆中最大的结点 swap( data[1] , data[count] );//令最大节点与最后一个节点交换 count --;//删除最大节点 shiftDown(1);//对刚刚交换上去的节点进行调整，使其符合最大堆的形式 return ret; } void shiftDown(int k) { while( 2*k <= count )//如果该节点有左孩子 { int j = 2*k;//左孩子的索引值 if( j+1 <= count && data[j+1] > data[j])//如果该节点有右孩子，并且右孩子的值大于左孩子 j ++;//更新为右孩子的索引值 if( data[k] >= data[j])//如果该大于他的孩子结点 break; swap(data[k],data[j]);//否则使该节点与孩子中最大的结点交换 k = j; } }};int main(){ int array[]={ 15,17,19,13,22,16,17,30,41,62}; Sort sort; int len = sizeof(array)/sizeof(array[0]); bool arr = sort.checkDuplicate(array,len); cout<
              
               <