寻找未排序数组中重复元素的最优时间复杂度算法

问题描述 #

给定包含n个元素的未排序数组，元素取值范围为1到n-1，其中恰好存在一个重复值，要求找到该重复元素并追求最优时间复杂度。

你提供的C++算法如下：

int tab[] = { 1,6,7,8,9,4,2,2,3,5 };
int arrSize = sizeof(tab)/sizeof(tab[0]);

for (int i = 0; i < arrSize; i++) {
    tab[tab[i] % arrSize] = tab[tab[i] % arrSize] + arrSize;
}

for (int i = 0; i < arrSize; i++) {
    if (tab[i] >= arrSize * 2) {
        std::cout << i;
        break;
    }
}

关于时间复杂度的上限 #

首先明确：不可能达到优于O(n)的时间复杂度。因为要确定重复元素，你至少需要遍历数组中的每个元素一次——假设存在算法只遍历少于n个元素，必然遗漏至少一个元素，而这个遗漏元素恰好可能是重复项，无法保证结果正确。所以O(n)是该问题的时间复杂度下限。

更优的算法（空间或操作效率优化） #

你的算法是O(n)时间、O(1)空间，但会修改原数组。以下是几种同样O(n)时间的优化方案：

1. 原地交换法（允许修改原数组）

逻辑更直观，无需取模和加法操作，常数时间开销更小：

int findDuplicate(int nums[], int n) {
    while (nums[0] != nums[nums[0]]) {
        std::swap(nums[0], nums[nums[0]]);
    }
    return nums[0];
}

2. 快慢指针法（Floyd判圈算法，不修改原数组）

利用数组元素取值特性，将数组视为带环链表，重复元素即为环的入口点，完全不改动原数组：

int findDuplicate(const int nums[], int n) {
    int slow = nums[0];
    int fast = nums[nums[0]];
    // 找到快慢指针相遇点
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    // 找到环的入口（重复元素）
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

3. 数学求和法（代码简洁，需注意溢出）

计算1到n-1的理论和，与数组实际求和的差值即为重复元素，代码最简洁，但n较大时可能出现数值溢出：

int findDuplicate(int nums[], int n) {
    int expectedSum = (n-1)*n / 2;
    int actualSum = 0;
    for (int i = 0; i < n; i++) {
        actualSum += nums[i];
    }
    return actualSum - expectedSum;
}

总结 #

所有正确算法的时间复杂度都是O(n)，这是问题的下限。你可以根据是否允许修改原数组、是否担心数值溢出等场景选择不同方案，它们在常数时间或空间特性上各有优劣，但时间复杂度无法再优化。

内容的提问来源于stack exchange，提问作者hero