重复值判断练习题

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

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

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

返回：true

 

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

 

#include <iostream>
#include <algorithm>
#include "string.h"
#include "stdio.h"
#include <vector>
#include <deque>
#include<stack>
#include <assert.h>
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<n;i++)
        {
            data[i+1] = a[i];//使堆的结点存入data数组中时下标是从1开始
        }
        count = n;
        //构造堆
        for( int i = count/2 ; i >= 1 ; i -- )//从树种第一个不是叶子结点的索引开始
            shiftDown(i);
        for( int i = n-1 ; i >= 0 ; i-- )
            a[i] = extractMax();
　　　　　//对排序后的数组做判断，是否存在重复的数字
        for(int i=0;i<n-1;i++)
        {
            if(a[i]==a[i+1])
                return true;
        }
        return false;
    }

    int extractMax()
    {
         assert(count>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<<arr<<endl;
    return 0;
}