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

Question

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

问题:编写一个时间和空间复杂度分别为 O(n) 和 O(1) 的 C++ 或 C 函数，在不改变给定数组的情况下找到重复整数。

示例:给定 {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));
}

Answer 1

big-O 表示法的定义是它的参数是一个函数 (f(x))，作为函数 (x) 中的变量，它倾向于无穷大，存在一个常数K，使得目标成本函数小于Kf(x)。通常，f 被选择为满足条件的最小这样的简单函数。 (很明显如何将上述内容提升为多个变量。)

这很重要，因为 K - 您不需要指定 - 允许将大量复杂行为隐藏在视线之外。例如，如果算法的核心是O(n²)，它允许其他各种O(1), O(logn), O(n), O(nlogn), O (n^3/2) 等支持要隐藏的位，即使对于真实的输入数据，这些部分实际上是占主导地位的部分。 没错，它可能完全具有误导性! (一些更高级的 bignum 算法确实具有此属性。与数学说谎是一件很棒的事情。)

那么这是怎么回事？好吧，您可以很容易地假设 int 是一个固定大小(例如，32 位)，并使用该信息来跳过很多麻烦并分配 fixed size 数组标记位以保存您真正需要的所有信息。实际上，通过每个潜在值使用两位(一位表示您是否已经看到该值，另一位表示您是否已打印它)，那么您可以处理具有 1GB 大小的固定内存块的代码。这将为您提供足够的标志信息来处理您可能曾经希望处理的尽可能多的 32 位整数。 (哎呀，这在 64 位机器上甚至是实用的。)是的，设置该内存块需要一些时间，但它是恒定的，因此它正式为 O(1)，因此退出分析。鉴于此，您将拥有恒定(但惊人)的内存消耗和线性时间(您必须查看每个值以查看它是否是新的、见过一次等)，这正是所要求的。

虽然这是一个肮脏的把戏。您也可以尝试扫描输入列表以计算出在正常情况下允许使用较少内存的范围；同样，这只会增加线性时间，您可以严格限制上述所需的内存，以便保持不变。还有更多的技巧，但在形式上是合法的。

---

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