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

[yigal_s]

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

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

Comments

Re: Для смеха

[dimrub.livejournal.com]

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

Re: Для смеха

[profi.livejournal.com]

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

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