Учитывая, что у вас есть массив A [1..n] размера n, он содержит элементы из набора {1..n}. Однако два элемента отсутствуют, (и, возможно, два из элементов массива повторяются). Найдите недостающие элементы.
Например, если n = 5, A может быть A [5] = {1,2,1,3,2}; и поэтому отсутствующие элементы {4,5}
Подход, который я использовал, был:
int flag[n] = {0};
int i;
for(i = 0; i < n; i++) {
flag[A[i]-1] = 1;
}
for(i = 0; i < n; i++) {
if(!flag[i]) {
printf("missing: %d", (i+1));
}
сложность пространства приходит к O (n). Я чувствую, что это очень детский и неэффективный код. Не могли бы вы предоставить лучший алгоритм с более сложной пространственной и временной сложностью.