Я не понимаю, чего мне не хватает в этом вопросе, но AFAIK. Я не вижу причины, по которой любое (разумное) решение должно быть чем-то большим или худшим, чем O(n) временная (и пространственная) сложность.
Из приведенных выше комментариев и ответов я понимаю следующее:
- Отрицательные числа: я не уверен, разрешены ли отрицательные числа или нет. ОП говорит
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 - это размер массива и должны присутствовать все числа от 0 до 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;
}