在O(n)时间和O(1)空间内找出重复的有符号整数

Question

(这是一个泛化版本：在O(n)时间和O(1)空间中查找重复项)

问题：编写一个C++或C函数，其时间和空间复杂度分别为O（n）和O（1），用于查找给定数组中的重复整数，而不改变它。

示例：给定{1，0，-2，4，4，1，3，1，-2}，函数必须打印1、-2和4一次（任意顺序）。

---

编辑：以下解决方案对于数组最小值到最大值范围内的每个整数都需要一个双位（以表示0、1和2）。所需的字节数（无论数组大小如何）永远不超过(INT_MAX - INT_MIN) / 4 + 1。

#include <stdio.h>

void set_min_max(int a[], long long unsigned size,\
                 int* min_addr, int* max_addr)
{
    long long unsigned i;

    if(!size) return;
    *min_addr = *max_addr = a[0];
    for(i = 1; i < size; ++i)
    {
        if(a[i] < *min_addr) *min_addr = a[i];
        if(a[i] > *max_addr) *max_addr = a[i];
    }
}

void print_repeats(int a[], long long unsigned size)
{
    long long unsigned i;
    int min, max = min;
    long long diff, q, r;
    char* duos;

    set_min_max(a, size, &min, &max);
    diff = (long long)max - (long long)min;
    duos = calloc(diff / 4 + 1, 1);
    for(i = 0; i < size; ++i)
    {
        diff = (long long)a[i] - (long long)min; /* index of duo-bit
                                                    corresponding to a[i]
                                                    in sequence of duo-bits */
        q = diff / 4; /* index of byte containing duo-bit in "duos" */
        r = diff % 4; /* offset of duo-bit */
        switch( (duos[q] >> (6 - 2*r )) & 3 )
        {
            case 0: duos[q] += (1 << (6 - 2*r));
                    break;
            case 1: duos[q] += (1 << (6 - 2*r));
                    printf("%d ", a[i]);
        }
    }
    putchar('\n');
    free(duos);
}

void main()
{
    int a[] = {1, 0, -2, 4, 4, 1, 3, 1, -2};
    print_repeats(a, sizeof(a)/sizeof(int));
}

- Apshir

---

当您的乘法溢出时，您的解决方案是否适用于大输入数组？ - parapura rajkumar

严格来说，您的解决方案既不是O(n)时间复杂度也不是O(1)空间复杂度。它会对{5,5,5,5,5,5,5}这种情况进行溢出处理。为了解决这个问题，您需要使用任意精度算术运算，它具有非O(1)时间和空间复杂度。 - Yakov Galka

我同意 @ybungalobill 的观点，你提出的解决方案不符合限制条件。例如，要适用于任何输入，您需要能够计算O(n)个质数，这要么需要一个表格占用O(n)的空间，要么在运行时计算需要O(n^2)的时间。 - caf

如果你的解决方案只是分配一个大数组（512MB足够为每个可能的32位数字留一些空间），那么你就有了恒定的空间。虽然不会很高效，但这是一种技术上正确的解决方案。 - Donal Fellows

@ybungalobill：但这就像是在一堵墙上撞头，而门却在三米开外。使用两个512MB的数组，_你不需要质数来解决32位整数的问题_。每个整数只需要两个标志位（“至少出现一次”，“至少出现两次”）。由于分配的内存没有考虑输入数据的大小，因此它必须是O(1)，但常数因子非常大。您还可以获得微不足道的O(n)时间行为。 - Donal Fellows

Answer 1

大O符号的定义是，它的参数是一个函数（f(x)），当函数中的变量（x）趋向于无穷大时，存在一个常数K，使得目标成本函数小于Kf(x)。通常选择f作为最小的简单函数，以满足条件。（很明显如何将以上内容扩展到多个变量。）

这很重要，因为你不需要指定K，它可以隐藏许多复杂行为。例如，如果算法的核心是O(n^2)，它允许所有其他O(1)，O(logn)，O(n)，O(nlogn)，O(n^3/2)等支持部分被隐藏，即使对于实际输入数据，这些部分实际上是主导因素。没错，它可能会完全误导你！（一些更高级的大数字算法确实具有这种特性。用数学欺骗人是一件美妙的事情。）

那么这是什么意思？好吧，你可以轻松地假设int是固定大小的（例如32位），并使用该信息跳过许多麻烦，并分配固定大小的标志位数组来保存您真正需要的所有信息。实际上，通过使用每个潜在值的两个位（一个位用于表示是否已经看到该值，另一个位用于表示是否已经打印了该值），则可以使用1GB大小的固定内存块处理代码。然后，这将为你提供足够的标志信息，以处理可能需要处理的尽可能多的32位整数。 （嘿，在64位机器上甚至也是实用的。）是的，设置该内存块需要一些时间，但它是常量，因此在分析中被忽略。考虑到这一点，您将拥有恒定（但惊人的）内存消耗和线性时间（您必须查看每个值，以查看它是否是新的，已经看过一次等），这正是所要求的。

这是一个卑鄙的技巧。您还可以尝试扫描输入列表以计算范围，从而在正常情况下使用更少的内存；同样，这只会增加线性时间，并且您可以像上面那样严格限制所需的内存。更多的技巧，但在形式上是合法的。

[编辑]示例C代码（这不是C ++，但我不擅长C ++；主要区别在于如何分配和管理标志数组）：

#include <stdio.h>
#include <stdlib.h>

// Bit fiddling magic
int is(int *ary, unsigned int value) {
    return ary[value>>5] & (1<<(value&31));
}
void set(int *ary, unsigned int value) {
    ary[value>>5] |= 1<<(value&31);
}

// Main loop
void print_repeats(int a[], unsigned size) {
    int *seen, *done;
    unsigned i;

    seen = calloc(134217728, sizeof(int));
    done = calloc(134217728, sizeof(int));

    for (i=0; i<size; i++) {
        if (is(done, (unsigned) a[i]))
            continue;
        if (is(seen, (unsigned) a[i])) {
            set(done, (unsigned) a[i]);
            printf("%d ", a[i]);
        } else
            set(seen, (unsigned) a[i]);
    }

    printf("\n");
    free(done);
    free(seen);
}

void main() {
    int a[] = {1,0,-2,4,4,1,3,1,-2};
    print_repeats(a,sizeof(a)/sizeof(int));
}

- Donal Fellows

---

这比预先计算前40亿个质数要容易得多... - Donal Fellows

我必须给你的答案点个赞。现在你能在C++函数中实现你的想法吗？这就是问题所要求的。 - Apshir

该代码还“强烈”假定使用32位的int，并且只适用于64位机器。幸运的是，许多系统现在都采用了I32LP64结构，并拥有足够的内存，因此有很大机会使其全部运行正常 :-) - Donal Fellows

没有输出的崩溃——在一台搭载i5处理器和6GB RAM的系统上。 - Apshir

@Afshin：是的，因为我在位操作上搞错了。这就展示了当我匆忙而不测试时会发生什么... - Donal Fellows

Answer 2

由于您拥有一个整数数组，因此可以使用对数组进行排序的简单解决方案（您没有说不能修改），并打印重复项。整数数组可以使用基数排序以 O(n) 时间复杂度和 O(1) 空间复杂度进行排序。虽然一般情况下可能需要 O(n) 的空间，但是使用原位二进制 MSD 基数排序可以轻松实现 O(1) 空间复杂度（在此处查看更多细节）。

- Konstantin Oznobihin

---

基数排序的空间复杂度是O(n)。 - David Brown

时间复杂度为什么是O(n)？ - a-z

@Konstantin Oznobihin：如何在整数上实现O(n)时间和O(1)空间的基数排序？（您应该解释得更多） - a-z

@DavidBrown：这不是就地二进制基数排序 http://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations。 - Konstantin Oznobihin

问题现在已经被编辑，禁止了原地排序，所以无论如何它已经不再相关。 - Steve Jessop

Answer 3

O(1) 空间限制是难以处理的。

打印数组本身就需要 O(N) 的存储空间，按照定义。

现在，我很慷慨，让你可以在程序中使用 O(1) 存储缓冲区，并认为程序外部占用的空间不是你关心的问题，因此输出不是问题...

但是，由于输入数组的不可变性约束，O(1) 空间限制仍然感觉难以处理。这可能并非如此，但它确实是这样感觉的。

而你的解决方案溢出了，因为你试图在有限的数据类型中记忆 O(N) 信息。

- Matthieu M.

Answer 4

这里有一个定义上的棘手问题。O(n)是什么意思？

Konstantin的回答声称基数排序的时间复杂度是O(n)。实际上它是O(n log M)，其中对数的底数是所选的基数，M是数组元素可能具有的值的范围。因此，例如，32位整数的二进制基数排序将具有log M = 32。

因此，在某种意义上，这仍然是O(n)，因为log M是与n无关的常数。但是如果我们允许这样做，那么就有一个更简单的解决方案：对于范围内的每个整数（共4294967296个），遍历数组以查看它是否出现多次。这在某种意义上也是O(n)，因为4294967296也是与n无关的常数。

我不认为我的简单解决方案算作答案。但如果不行，那么我们也不应该允许基数排序。

- TonyK

Answer 5

我怀疑这是不可能的。假设有解决方案，让我们看看它是如何工作的。我会尽量通俗易懂地解释为什么它行不通...那么，它是如何工作的呢？

不失一般性，我们可以说我们处理数组k次，其中k是固定的。当存在m个重复项时，解决方案也应该适用，其中m >> k。因此，在至少一次遍历中，我们应该能够输出x个重复项，其中x随着m的增长而增长。为了做到这一点，在先前的遍历中计算了一些有用的信息，并存储在O(1)的存储器中。（不能使用数组本身，这将给出O(n)的存储空间。）

问题在于：我们只有O(1)的信息，当我们遍历数组时，我们必须识别x个数字（以便输出它们）。我们需要一个O(1)的存储器，可以告诉我们一个元素是否在其中，需要O(1)的时间。或者换句话说，我们需要一种数据结构来存储n个布尔值（其中x个为true），它使用O(1)的空间，并且需要O(1)的时间来查询。

这种数据结构存在吗？如果不存在，那么我们就无法在O(n)时间和O(1)空间内找到数组中的所有重复项（或者有一些花哨的算法可以以完全不同的方式工作吗？）。

- Ishtar

Answer 6

我真的不明白如何只使用O(1)空间而不修改初始数组。我的猜测是你需要一个额外的数据结构。例如，整数的范围是多少？如果像你链接的另一个问题一样是0..N，那么你可以有一个大小为N的附加计数数组。然后在O(N)中遍历原始数组并增加当前元素位置的计数器。然后遍历其他数组并打印计数>=2的数字。类似这样：

int* counts = new int[N];
for(int i = 0; i < N; i++) {
    counts[input[i]]++;
}

for(int i = 0; i < N; i++) {
    if(counts[i] >= 2) cout << i << " ";
}

delete [] counts;

- Tudor

Answer 7

假设您可以利用未使用所有空间的事实。 您只需要每个可能值多一个位，并且您在32位 int 值中有许多未使用的位。

这种方法存在严重限制，但在这种情况下有效。 数字必须介于 -n/2 和 n/2 之间，如果它们重复出现 m 次，则将打印 m/2 次。

void print_repeats(long a[], unsigned size) {
    long i, val, pos, topbit = 1 << 31, mask = ~topbit;
    for (i = 0; i < size; i++)
        a[i] &= mask;

    for (i = 0; i < size; i++) {
        val = a[i] & mask;
        if (val <= mask/2) {
           pos = val;
        } else {
            val += topbit;
            pos = size + val;
        }
        if (a[pos] < 0) {
            printf("%d\n", val);
            a[pos] &= mask;
        } else {
            a[pos] |= topbit;
        }
    }
}

void main() {
    long a[] = {1, 0, -2, 4, 4, 1, 3, 1, -2};
    print_repeats(a, sizeof (a) / sizeof (long));
}

打印

4
1
-2

- Peter Lawrey

---

那个不起作用。尝试使用 long a[] = { 10000000 } ;（请参见 http://ideone.com/I5IZr 获取结果）。 - TonyK

你是对的，抱歉。(但你也是对的，称它为严重限制！) - TonyK