![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
yigal_sДан массив из N элементнов. Ну, к примеру, integers
Делается копия этого массива, элементы в ней случайно перемешиваются, а 4 элемента просто выкидываются.
Теперь у нас имеется два массива - из N и N-4 элементов.
-----
Требуется - быстро найти значения удаленных четырёх элементов.
Upd: дополнительное условие - не аллоцировать дополнительных массивов.
Делается копия этого массива, элементы в ней случайно перемешиваются, а 4 элемента просто выкидываются.
Теперь у нас имеется два массива - из N и N-4 элементов.
-----
Требуется - быстро найти значения удаленных четырёх элементов.
Upd: дополнительное условие - не аллоцировать дополнительных массивов.
Re: В лоб
Date: 2007-01-30 07:48 am (UTC)Объем кэша - это O(N). Я хотел услышать решение без кэша (вот только сразу позабыл упомянуть в условии требование экономии памяти)