找到时间为O(n)且空间为O(1)的有符号整数

Question

(这是一个概括:在O(n)时间和O(1)空间中查找重复项)

问题:分别编写具有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位)并使用该信息来避免很多麻烦并分配固定大小的标志位数组来保存你真正需要的所有信息.实际上,通过每个潜在值使用两位(一位表示您是否已经看到该值,另一位表示您是否已经打印它),您可以使用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));
}

Answer 2

由于你有一个整数数组,你可以使用简单的解决方案来排序数组(你没有说它不能被修改)和打印重复.可以使用Radix排序使用O(n)和O(1)时间和空间复杂度对整数数组进行排序.虽然通常它可能需要O(n)空间,但是就地二进制MSD基数排序可以使用O(1)空间来简单地实现(在这里查看更多细节).