重复值判断练习题

题目

请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。
给定一个int数组A及它的大小n，请返回它是否有重复值。

思路

空间复杂度为O（1）的在三种非平方级的排序算法中只有堆排序，所以这里选择先使用堆排序进行排序，然后通过遍历过程前后置判断是否重复来解决

答案

void swapVector(int i, int j, vector<int> &A) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void adjustMaxHeap(vector<int> &A, int start, int end) {
    for (int current = start, left = start * 2 + 1; left <= end; current = left, left = left * 2 + 1) {
        if (left < end && A[left] < A[left + 1]) {
            left++;
        }
        if (A[current] < A[left]) {
            swapVector(current, left, A);
        } else {
            break;
        }
    }
}

void heapSort(vector<int> &A, int n) {
    // 构建大顶堆
    for (int i = n/2 - 1; i >= 0; i--) {
        adjustMaxHeap(A, i, n - 1);
    }
    
    // 调整大顶堆
    for (int i = n - 1; i > 0;) {
        swapVector(0, i, A);
        adjustMaxHeap(A, 0, --i);
    }
}

bool checkDuplicate(vector<int> a, int n) {
    // 利用迭代的堆排序算法进行排序O(logn * n)
    heapSort(a, n);
    
    // 判断是否有相同的值
    for (int i = 0; i < n - 1; i++) {
        if (a[i] == a[i + 1]) {
            return true;
        }
    }
    return false;
}