找到时间为O（n）且空间为O（1）的有符号整数
（这是一个概括： 在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 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] *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 > (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（n 2 ），它允许各种其他O（1），O（logn），O（n），O（nlogn），O（n 3/2 ），支持要隐藏的位， 即使对于真实的输入数据，这些部分实际上是主导的。 没错，这可能完全是误导！ （一些更高级的bignum算法具有真实的这个属性。用数学说谎是一件很棒的事情。）
那么这是怎么回事？ 好吧，您可以假设int是一个足够容易的固定大小（例如，32位）并使用该信息来跳过很多麻烦并分配固定大小的标志位数组来保存您真正需要的所有信息。 实际上，通过每个潜在值使用两位（一位表示您是否已经看到该值，另一位表示您是否已打印它），您可以使用1GB大小的固定内存块来处理代码。 然后，它将为您提供足够的标记信息，以处理您可能希望处理的32位整数。 （哎呀，这在64位机器上实际上是可行的。）是的，它需要一些时间来设置内存块，但它是不变的，所以它正式为O（1），因此退出分析。 鉴于此，您可以获得恒定（但非常高）的内存消耗和线性时间（您必须查看每个值以查看它是否是新的，一次看到的等等），这正是所要求的。
虽然这是一个肮脏的把戏。 您也可以尝试扫描输入列表以计算范围，从而允许在正常情况下使用更少的内存; 再次，只增加线性时间，你可以严格限制上面所需的内存，这是常量。 更狡猾，但正式合法。
[编辑]示例C代码（这不是C ++，但我不擅长C ++;主要区别在于如何分配和管理标志数组）：
#include #include // 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
由于你有一个整数数组，你可以使用直接的解决方案来排序数组（你没有说它不能被修改）和打印重复。 可以使用Radix排序使用O（n）和O（1）时间和空间复杂度对整数数组进行排序 。 虽然通常它可能需要O（n）空间，但是就地二进制MSD基数排序可以使用O（1）空间来简单地实现（ 在这里查看更多细节）。
O（1）空间约束是难以处理的。
根据定义，打印arrays本身的事实需要O（N）存储。
现在，感觉很慷慨，我会告诉你，你可以在你的程序中有一个缓冲区的O（1）存储空间，并认为程序之外的空间与你无关，因此输出不是问题…
尽管如此，由于输入数组的不变性约束，O（1）空间约束感觉难以处理。 它可能不是，但感觉如此。
并且您的解决方案溢出，因为您尝试以有限数据类型记忆O（N）信息。
这里的定义有一个棘手的问题。 O（n）是什么意思？
Konstantin的回答声称基数排序时间复杂度为O（n）。 实际上它是O（n log M），其中对数的基数是所选择的基数，M是数组元素可以具有的值的范围。 因此，例如，二进制基数排序的32位整数将具有log M = 32。
因此，在某种意义上，这仍然是O（n），因为log M是一个独立于n的常数。 但是如果我们允许这个，那么有一个更简单的解决方案：对于范围内的每个整数（所有4294967296），遍历数组以查看它是否多次出现。 从某种意义上说，这也是O（n），因为4294967296也是一个独立于n的常数。
我不认为我的简单解决方案会算作答案。 但如果没有，那么我们也不应该允许基数排序。
我怀疑这是可能的。 假设有一个解决方案，让我们看看它是如何工作的。 我会努力做到尽我所能，并certificate它无法运作……那么，它是如何运作的？
在不失一般性的情况下，我们可以说我们处理数组k次，其中k是固定的。 当有m个重复时，解决方案也应该有效，m >> k。 因此，在至少一个传递中，我们应该能够输出x个重复，其中x在m增长时增长。 为此，在先前的传递中计算了一些有用的信息并存储在O（1）存储器中。 （不能使用数组本身，这会产生O（n）存储。）
问题是：我们有O（1）信息，当我们遍历数组时，我们必须识别x数字（输出它们）。 我们需要O（1）存储，而不是在O（1）时间内告诉我们，如果元素在其中。 或者以不同的方式说，我们需要一个数据结构来存储使用O（1）空间的n个布尔（其中x是true ），并且需要O（1）时间来查询。
这个数据结构是否存在？ 如果没有，那么我们找不到具有O（n）时间和O（1）空间的数组中的所有重复项（或者有一些奇特的算法以完全不同的方式工作???）。
我真的不知道如何只有O（1）空间而不修改初始数组。 我的猜测是你需要一个额外的数据结构。 例如，整数的范围是多少？ 如果它与您链接的其他问题中的0..N相似，则可以使用大小为N的附加计数数组。然后在O（N）中遍历原始数组并在当前元素的位置递增计数器。 然后遍历另一个数组并使用count> = 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;
假设您可以使用您没有使用所有空间的事实。 每个可能的值只需要一个位，并且在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