这个问题是针对真正的聪明人的，因为它应该在没有辅助阵列的情况下完成，并且必须是最有效的！
C 程序 - 需要接收一个包含 X 个数字的数组（假设 X=4 数组：5,4,3,2）并检查数组是否包含从 0 到 X-1 的所有数字（如果 X 是 44，则需要检查如果数组内的所有数字都在 0 到 43 之间）。
它必须非常高效——我的意思是，在阵列上运行 43 次不是一种选择！
你知道怎么做吗？我试图弄清楚这个几个小时而没有任何成功！
它必须是 O(n)。
问问题
1098 次
12 回答
2
如果允许更改数组的顺序，您可以使用就地排序算法，然后检查是否有一些 i：
array[i] == array[i+1]
那么时间复杂度可以是 O(n*lg n)。
于 2012-01-03T12:09:38.730 回答
1
您可以将问题简化为查找重复项。
证明：
- 如果数组的长度不是 X => 缺少数字。您可以在 O(1) 或 O(n) 中轻松检查。
- 否则 => 您要么拥有所有正确的数字，要么有重复的数字。
有了它，您可以使用此实现：在 O(n) 时间和 O(1) 空间中查找重复项。还要确保检查数组的边界。如果数字不在边界内，则数组包含不正确的数字。
这导致 O(n) 解决方案。
于 2012-01-03T10:36:33.833 回答
1
对两个数组进行排序（在 中O(n log n)）。然后将两个数组都视为队列：
- 如果两个队列的头元素相等，则打印其中一个并弹出两者。
- 如果头部元素不相等，则弹出较小的元素。
- 重复。
于 2012-01-03T13:43:35.300 回答
0
您可以对数组进行排序，然后扫描一次。这应该给你 O(N log N) 的性能，比你需要的天真的方法更好的 O(N^2)。
于 2012-01-03T09:53:15.797 回答
0
在此处查看一些出色的答案，@caf 答案的 C++ 实现可能是
bool stop=true;
// 首先将元素 i 放在位置 A[i]，即 4 在 A[4]
for(int i = 0; i<n; i++) {
while (A[A[i]] != A[i]){
swap(A[i], A[A[i]])
}
}
// than u can have the second loop which does the decision
for(int i = 0; i<n && !stop; i++) {
if (A[i] != i){
stop = true;
}
}
if (stop)
printf("duplicate");
else
printf("not duplicate)
于 2012-01-03T12:04:33.807 回答
0
foreach(int i in array)
{
int count = 0;
foreach(int i2 in array)
{
if(i == i2)
{
count++;
}
}
if(count > 1)
{
return false;
}
}
return true;
于 2012-01-03T12:05:53.650 回答
0
一个 O(n) 解决方案：该算法尝试将数组中的每个元素放在其正确的位置，例如，1 放在 a[0] 上，2 放在 a[1] 上，方法是与占据原点位置的元素交换。
一开始，i = 1, a[i - 1] = 1，没关系，什么都不会碰
i = 1
a = 1 6 3 4 5 7 1
然后，i = 2, a[i - 1] = 6 != 2，然后交换 a[i - 1] 和 a[6 - 1]
i = 2
a = 1 7 3 4 5 6 1
那么，i 仍然是 2，但是 a[i - 1] == 7 != 2，然后交换 a[i - 1] 和 a[7 - 1]
i = 2
a = 1 1 3 4 5 6 7
现在 i = 2 但我们看到 a[i - 1] == a[1 - 1]，因此我们找到了重复项
完整来源：
#include <stdio.h>
int main() {
int a[7] = {1, 6, 3, 4, 5, 7, 1};
int i, t;
for (i = 0; i < 7; ++i) {
while (a[i] != i + 1) {
if (a[i] == a[a[i] - 1]) {
printf("duplicate: %d\n", a[i]);
goto out;
}
t = a[i];
a[i] = a[a[i] - 1];
a[t - 1] = t;
}
}
printf("no duplicate\n");
out:
return 0;
}
于 2012-01-03T12:27:59.463 回答
0
如果数组都已排序，则可以使用修改后的合并操作（如合并排序中使用的合并操作）。
于 2012-01-03T13:40:59.833 回答
0
[在平均情况下] 你可以比建议的O(nlogn)解决方案做得更好。
有一个O(n)使用哈希表的机械化平均案例解决方案：
hash <- new hash set
for each e in A:
hash.add(e)
for each e in B:
if hash.contains(e): print e
如果它们在 B 中出现两次，您可以通过存储额外的“打印”元素散列集来克服打印两次元素。
如果延迟或最坏情况下的性能问题是一个问题，请使用建议的排序和迭代解决方案之一。
于 2012-01-03T13:44:22.900 回答
0
对较小的进行排序并使用二进制搜索来搜索较大的每个元素。这样，您可以在数组的大小在O((n1+n2)*log(n1))哪里（较小）。n1, n2n1
于 2012-01-03T13:45:45.043 回答
-1
我不明白我在这个问题中遗漏了什么，但我不明白为什么任何（合理的）解决方案应该比O(n)时间（和空间）复杂性更多/更差的原因。
从以上评论和答案中，我了解到以下内容：
- 负数：我不确定是否允许负数。OP说
check if all the array has all the numbers from 0 to X-1。因此，数组中不会出现任何小于0预期的内容。所以我假设不允许负数 - 重复数字：引用来自 OP 的相同引用 -
check if all the array has all the numbers from 0 to X-1我猜如果X是数组的大小并且应该存在从0to的所有数字X-1，我猜不允许重复数字。
因此，做出上述假设，我们可以使用一位来检查i( 0 <= i <= X-1) 是否存在。如果i是重复的，那么它将无法提及有重复的数字。
它扫描整个数组一次 -O(n)每个元素只使用一位，所以X需要10这些X位 - 例如考虑我们需要处理1000000元素，sizeof(int)然后4我们需要3.82M内存来保存数组元素并且仅0.48M用于存储元素的存在。
#include <stdio.h>
#define X 10
#define MIN 0
#define MAX X-1
int main(void)
{
//int arr[X] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
//int arr[X] = {6, 7, 8, 9, 0, 5, 3, 2, 11, 12};
//int arr[X] = {1, 1, 2, 4, 5, 6, 7, 8, 2, 2};
int arr[X] = {1, 3, 2, 4, 5, 6, -7, 8, 2, 2};
/* if X is more than sizeof(int) then change
the flag type to a wider one! */
int flag = 0;
int i;
for(i=0 ;i<X ; i++) {
if (arr[i] >= MIN && arr[i] <= MAX) {
if (flag & 1<<arr[i]) {
printf("Duplicate found : %d \n", arr[i]);
return -1;
}
flag |= 1<<arr[i];
} else {
printf("Failure at %d : %d \n", i, arr[i]);
return -1;
}
}
printf("Success \n");
return 0;
}
于 2012-01-03T11:07:36.693 回答
-1
阅读此答案以获得答案 -数组验证 - 不使用辅助数组
一个由 n 个元素组成的数组，其中包含从 0 到 n-1 的元素，其中任何数字出现任意次数。
例如，设 n 为 7，数组为 {1, 2, 3, 4, 5, 4, 6}，答案应为 FALSE
上面的说法是不是自相矛盾？！
于 2012-01-03T11:13:56.127 回答