есть массив из N целых чисел от 0 до N. Каждое число из массива повторяется в нем 1 раз, кроме 0 (нуля) — он может встретиться сколько угодно раз. Задача — найти недостающие числа массива (в диапазоне от 1 до N) вместо которых стоит 0. Использовать в качестве вспомогательных только простые целочисленные переменные. Скорость роста алгоритма O(N) = N

пример: n=5, 0 2 4 1 0
решение: 3 5

Сначала думал посчитать хэш: T = X1 XOR X2 ... (Xn != 0), и заодно хэш универсума U = 1 XOR 2 XOR ... XOR N. Тогда T XOR U — это есть хэш недостающих элементов.. только вот как из него просто повыдирать элементы не додумался, похоже нельзя. Если есть такой способ решения — будет интересно.

Здравствуйте, free.rFczZZ, Вы писали:

FR>есть массив из N целых чисел от 0 до N. Каждое число из массива повторяется в нем 1 раз, кроме 0 (нуля) — он может встретиться сколько угодно раз. Задача — найти недостающие числа массива (в диапазоне от 1 до N) вместо которых стоит 0. Использовать в качестве вспомогательных только простые целочисленные переменные. Скорость роста алгоритма O(N) = N

Если массив можно разрушать, то всё очень просто.
Выполняем дефрагментацию, а потом пробегаем и смотрим, где нули.

int arr[N];

for(int i=1; i<=N; ++i)
{
  int& here = arr[i-1];
  while(here != 0 && here != i)
    swap(here, arr[here-1]);
    // после этой операции текущий элемент оказывается на своём месте
    // поэтому число элементов, стоящих не на своём месте, убывает;
}

for(int i=1; i<=N; ++i)
{
  int const& here = arr[i-1];
  if(here == 0)
    cout << "отсутствует число " << i << endl;
}

К>for(int i=1; i<=N; ++i)
К>{
К> int& here = arr[i-1];
К> while(here != 0 && here != i)
К> swap(here, arr[here-1]);
К>}

Отлично, спасибо! Когда думал о этом варианте решил что скорость будет n!. чета меня зациклило на бинарной арифметике.

Здравствуйте, Кодт, Вы писали:

К>Если массив можно разрушать, то всё очень просто.
Столь же несложное решение есть, если содержимое массива можно просто менять в процессе работы (но в конце оно должно вернуться в исходное положение). А именно: можно считать, что у нас появился бесплатный массив флажков размера n. Например, если нужно взвести i-й флажок, то добавим n к i-ой ячейке исходного массива. А с таким вспомогательным массивом легко решить задачу с помощью подсчета. В конце, когда ответ выписан, флажки можно сбросить.