программизм: вот такая задачка образовалась

[yigal_s]

Дан массив из N элементнов. Ну, к примеру, integers
Делается копия этого массива, элементы в ней случайно перемешиваются, а 4 элемента просто выкидываются.
Теперь у нас имеется два массива - из N и N-4 элементов.
-----
Требуется - быстро найти значения удаленных четырёх элементов.

Upd: дополнительное условие - не аллоцировать дополнительных массивов.

Comments

Для смеха

[profi.livejournal.com]

Я не программист. Да и арифметику подзабыл. :-)

Просто, чтобы проверить себя. Если оба массива упорядочить по одному и тому же закону, а потом вычесть поэлементно. Все ненулевые значения в массиве разности - это удаленные. Да? Нет? Только не бейте сапогами по голове! :-)))))

Re: Для смеха

[dimrub.livejournal.com]

Упорядочить - это O(n log n). Что, может быть, и не так уж плохо (в зависимости от специфики вопроса), но по умолчанию в такого рода задачах предполагается оптимальное асимптотическое решение (например - линейное).

Re: Для смеха

[profi.livejournal.com]

Да, конечно. Я просто привык к софту типа Ориджин, в качестве пользователя. А вот о том, что там внутри работает - забываю.

ПС Да, забыл еще укороченный массив дополнить нулями. Чтобы матрицы (илив векторы) были одинаковых размерностей. Но это уже не актуально. :-)

Re: Для смеха

[haraz-bey.livejournal.com]

Оба упорядочить по одному закону и сравнивать (вычитать) почленно. При каждом фолсе (ненулевом значении вычитания) текущий член большего массива заносится в список вычтенных, а счетчик меньшего массива вместо одного накручивает два.

[yigal_s]

правильно. Но упорядочивать массивы - слишком долго.

[haraz-bey.livejournal.com]

Это да. Я имел в виду, что если сравнивать таким образом, то нужен сдвиг. Можно было бы проверить каждый элемент из первого массива на наличие во втором, но это действительно для двух любых массивов, значит, мы теряем преимущество, заключающееся в дополнительных данных, известных о конкретных массивах. А вот как его использовать - надо еще подумать :)

[dr-tambowsky.livejournal.com]

Упорядочивать долго, но если не пользоваться никаким упорядочиванием (или чем-то в данном контексте эквивалентным типа хэш-таблицы, как предлагалось выше), то, казалось бы, время должно быть О(N^2), что всяко ещё хуже. Разве не так?

[haraz-bey.livejournal.com]

Разве что математический путь. У нас есть четыре неизвестных, есть их сумма (сумма одного массива минус сумма второго), есть суммы их же степеней. Но не знаю, намного ли это будет быстрее (особенно для программиста).