我正在尝试编写一个函数(用 C 语言(来检查数组是否具有所有元素(在 0 和它的"size-1"之间(
例如，如果数组的大小为 3，则它应该按任意顺序{0, 1, 2 }。
问题是：在没有额外阵列的情况下执行此操作的最有效复杂性是什么？
如下所示，我尝试的复杂性是(nlogn + n 的平均值(。 编辑：抱歉错过了理解，任何整数都可以是输入，这意味着检查大小不起作用 --> {0， 0， 3}
int check_missing_element(int *a, int n)
{
int i = 0;
quicksort(a, 0, n - 1);
for (i = 0; i < n; i++)
{
if (a[i] != i)
return 0;
}
return 1;
}
使用元素的值 [0...n-1] 作为下一个要访问的元素遍历数组。
离开每个元素时，将其值设置为n。 任何带有n的访问元素都已被访问过，因此是失败的 - 除非我们自己编制了索引。 任何值在 [0...n-1] 之外的元素都是失败的。
在"n"访问之后，我们就完成了。 O(n(。
不需要排序。 这确实会消耗阵列。
这是chux答案中勾勒的周期追逐算法的实现，以及一个测试程序。
/* Return 1 iff each integer in 0...n-1 appears exactly once in a[0]...a[n-1].
Return 0 otherwise.
*/
int check_missing_element(int *a, int n)
{
// Reject elements that are out of bounds.
for (int i = 0; i < n; ++i)
if (a[i] < 0 || n <= a[i])
return 0;
// Define a value to mark already seen values with.
static const int AlreadySeen = -1;
// Work through the array.
for (int i = 0; i < n; ++i)
// If we already examined this element, ignore it.
if (a[i] != AlreadySeen)
{
/* Follow the cycle defined by x -> a[x]. If we encounter an
already seen element before returning to i, report rejection.
Otherwise, mark each encountered element seen.
*/
for (int j = a[i]; j != i;)
{
int next = a[j];
if (next == AlreadySeen)
return 0;
a[j] = AlreadySeen;
j = next;
}
}
// Every element has been seen once and only once. Report acceptance.
return 1;
}
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Define a comparator for sorting int values in ascending order.
static int Comparator(const void *a, const void *b)
{
int A = * (const int *) a;
int B = * (const int *) b;
return
A < B ? -1 :
A == B ? 0 :
+1;
}
// Provide a reference routine for testing check_missing_elements.
static int check_missing_elementReference(int *a, int n)
{
/* Sort the elements. Iff the array contains each value exactly once,
this results in an array containing 0, 1, 2, 3,... n-1.
*/
qsort(a, n, sizeof *a, Comparator);
// Test the sorted array.
for (int i = 0; i < n; ++i)
if (a[i] != i)
return 0;
return 1;
}
#define ArrayLimit 7
#define NumberOf(a) (sizeof (a) / sizeof *(a))
/* Define a structure used to iterator through test values.
The indices in the Index array will each run from -x to n, inclusive,
where x is the number of special values (defined below) and n is the array
size. The indices will be incremented lexicographically (odometer style).
For the indices from -x to -1, the associated value will be one of the
special values. For the indices from 0 to n, the associated value will
equal the index. Note that n is outside the bounds of array values that
pass the test. It is included in testing so that rejections based on it
are tested.
*/
typedef struct
{
int Index [ArrayLimit];
int Values[ArrayLimit];
} Iterator;
// Define special values to include in testing.
static const int SpecialValues[] = { INT_MIN, -1, INT_MAX };
/* Define the number of special values as an int, not a size_t, because we use
its negation and so need a signed type.
*/
#define NumberOfSpecialValues ((int) NumberOf(SpecialValues))
// Initialize an iterator.
static void InitializeIterator(Iterator *Iterator, int n)
{
for (int i = 0; i < n; ++i)
{
Iterator->Index [i] = -NumberOfSpecialValues;
Iterator->Values[i] = SpecialValues[0];
}
}
/* Increment an iterator. Return 0 if we are done (all fields rolled over,
bringing the iterator back to the initial state) and 1 otherwise.
*/
static int Increment(Iterator *Iterator, int n)
{
// Start at the rightmost field.
int j =n-1;
while (0 <= j)
{
// If this field has room to increase, increment it.
if (Iterator->Index[j] < n)
{
++Iterator->Index[j];
/* Set the associated value to either a special value or the
index value, as described above.
*/
Iterator->Values[j] =
Iterator->Index[j] < 0
? SpecialValues[Iterator->Index[j] + NumberOfSpecialValues]
: Iterator->Index[j];
// There is no carry into the next field, so we are done.
return 1;
}
/* This field rolls over and resets to its initial value. Then we
carry into the next field.
*/
Iterator->Index [j] = -NumberOfSpecialValues;
Iterator->Values[j] = SpecialValues[0];
--j;
}
// All fields rolled over, so we are done.
return 0;
}
// Print an array.
static void PrintArray(int *a, int n)
{
printf("[");
if (0 < n)
printf("%d", a[0]);
for (int i = 1; i < n; ++i)
printf(", %d", a[i]);
printf("]");
}
int main(void)
{
// Test each array size up to the limit.
for (int n = 1; n <= ArrayLimit; ++n)
{
// Iterator through all array values.
Iterator i;
for (InitializeIterator(&i, n); Increment(&i, n);)
{
/* Since the routines destroy the array, copy the array. Then
execute the routine and record the return value.
*/
int Buffer[ArrayLimit];
// Reference routine first.
memcpy(Buffer, i.Values, n * sizeof *Buffer);
int expected = check_missing_elementReference(Buffer, n);
// Subject routine.
memcpy(Buffer, i.Values, n * sizeof *Buffer);
int observed = check_missing_element (Buffer, n);
// Test for a bug.
if (expected != observed)
{
printf("Failure:n");
printf("tArray = "); PrintArray(i.Values, n); printf("n");
printf("tExpected %d but observed %d.n", expected, observed);
exit(EXIT_FAILURE);
}
}
printf("Array length %d: Passed.n", n);
}
}