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

[yigal_s]

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

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

Comments

Re: Для смеха

[haraz-bey.livejournal.com]

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

[yigal_s]

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

[haraz-bey.livejournal.com]

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

[dr-tambowsky.livejournal.com]

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

[haraz-bey.livejournal.com]

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