Быстрая структура
Программистам
55
8
Решили 0.4% из 47905
16.12.2011
Некая структура хранит массив данных длиной N. У нее есть 3 метода работы с данными:
get(index) возвращает элемент по индексу,
set(Element, index) устанавливает значение по заданному индексу и
setAll(Element) устанавливает данное значение для всех элементов.
Надо написать эти три функции так, чтобы каждая из них работала за O(1). Выделение нового массива, заполнение массива через функции типа memset и т. п. работает за O(N). Можно использовать любые дополнительные переменные/массивы в самой структуре.
Поделиться
47 комментариев