c++ - 查找时间为O(n)，空间为O(1)的重复有符号整数

(这是对Finding duplicates in O(n) time and O(1) space的概括)

问题:编写一个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));
}

最佳答案

big-O表示法的定义是，其自变量是一个函数(f(x))，由于该函数(x)中的变量趋于无穷大，因此存在一个常数K，因此目标成本函数将小于Kf(x)。通常，将f选择为最小的此类简单函数，以便满足条件。 (很明显，如何将以上内容提升为多个变量。)

这很重要，因为不必指定K即可隐藏整个复杂的行为。例如，如果算法的核心是O(n2)，则它允许其他各种O(1)，O(logn)，O(n)，O(nlogn)，O(n3/2)等。支持位被隐藏，即使对于实际的输入数据，那些部分实际上是占主导地位的。没错，这可能完全是误导! (一些更出色的bignum算法具有真实的属性。与数学一起说谎是一件很棒的事情。)

那么这要去哪里呢？好吧，您可以轻松地假设int是固定大小的(例如32位)，并使用该信息来跳过很多麻烦，并分配固定大小的标志位数组来保存您真正需要的所有信息。实际上，通过每个潜在值使用两位(一位代表您是否已经看过该值，另一位代表您是否已打印出该值)，则可以使用大小为1GB的固定内存块来处理代码。然后，这将为您提供足够的标志信息，以应付您可能希望处理的尽可能多的32位整数。 (这在64位计算机上甚至是实用的。)是的，设置该内存块将花费一些时间，但是它是恒定的，因此它的形式为O(1)，因此退出了分析。鉴于此，您将拥有不变的(但惊人的)内存消耗和线性时间(您必须查看每个值以查看它是否是新值，见过一次等等)，而这正是所要的。

不过这是一个肮脏的把戏。您也可以尝试扫描输入列表以计算出范围，从而在正常情况下可以使用较少的内存。同样，这只会增加线性时间，并且您可以严格限制上述所需的内存，因此它是恒定的。更加棘手，但是正式合法。

[编辑]示例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));
}

关于c++ - 查找时间为O(n)，空间为O(1)的重复有符号整数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8208363/