如何在 Java 的 O(1) 时间内找到数组中的重复项？

Question

我接到一项任务，要在 O(1) 时间内在 int 数组中查找重复项。 我的方法是先对数组进行排序，然后使用线性搜索找到重复项。我首先通过交换数字对数组进行排序，如下所示：

for(int i = 0;i<ar.length;i++) {
    for (int j = i + 1; j < ar.length; j++) {
        if (ar[i] > ar[j]) {
            buk = ar[i];
            ar[i] = ar[j];
            ar[j] = buk;
        }
    }
}

但此算法的效率为 O(i*j)，这不是解决方案所必需的。我尝试使用递归对数组进行排序：

static int x = 0;
static int[] swap(int[] arr) {
    if (x >= arr.length)
        return arr;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i - 1] > arr[i]) {
            int bucket = arr[i - 1];
            arr[i - 1] = arr[i];
            arr[i] = bucket;
        }
    }
    x++;
    arr = swap(arr);
    return arr;
}

但这目前似乎不起作用。请提供suggestions/alternate方法对数组进行排序，这个问题我遇到过很多次了。

问题是：使用小于 O(n) space 并按顺序遍历流 O(1) 次，找到一个在线性时间内重复的数字。

Answer 1

从数学上讲不可能在 O(1) 中找到重复项。您必须检查数组的所有 N 个元素 至少一次 以测试每个元素是否重复。那是至少 N 操作，所以下限复杂度是 O(N).

提示：如果您使用（比如说）HashSet 来记录您已经看到的每个值，则可以在 O(N) 中执行此操作。问题是 HashSet 是一个 space-hungry 数据结构。

Please provide suggestions/alternate methods to sort an array, I have encountered this problem many times.

对整数数组进行排序的简单方法是使用 Arrays::sort(int[])。那将是 O(NlogN)。

理论上可以比 O(NlogN) 更好地对整数数组进行排序，但前提是您可以限制整数的范围。查找 counting sort。复杂度为 O(max(N, R)，其中 R 是最小数和最大数之间的差值。问题是 O(R) 可能比 O(N) 大得多……取决于输入。

但是如果你知道 M 可能小于 NlogN，你可以使用计数排序的变体，只使用额外的 O(M) 位 space 到 de-duplicate O(max(M, N)) 中的数组。（我会留给你弄清楚细节。）

如何在 Java 的 O(1) 时间内找到数组中的重复项？

How to find the duplicates in an array in O(1) time in Java?

java

sorting

algorithm

performance

compare-and-swap