Panshin,

Кто-то сказал, что число 36 253 в этой последовательности есть?

Требуется указать число, либо его индекс в некотором массиве. Возможных индексов - n, чисел - 1000000.
Если отсортировать массив (O(n*ln(n))), то проверка каждого индекса на правильность - O(1).

Каким свойством вместо монотонности может обладать массив, чтобы наличие дубликатов элемента по заданному индексу проверялось за O(1)?

Nitica,

Бедный процессор.
И вообще, если массив "по умолчанию" заполнен нулями, то, позвольте спросить, кто его заполнил?

DENIS_CHELИсходный массив с числами произвольной длины... Но не больше 1 000 000.
1 000 001 ;)

JoFanПока приходит на ум какая нибудь быстрая сортировка, где в операции сравнения и будем проверять на равенство
Быстрые сортировки потому и быстрые, что сравнивают друг с другом не все n(n-1)/2 пар.

NiticaAbstraction,
Бедный процессор.

то есть сортировка, по Вашему мнению, менее затратна, чем просто один пробег по массиву. Указатели - самое менее затратное средство в вычислениях как ни крути :)

И вообще, если массив "по умолчанию" заполнен нулями, то, позвольте спросить, кто его заполнил?

это псевдо-код :) в Visual C, например, точно будут нулики
Массив в 500 элементов, а мы отжираем 2 Mb. Спорный выигрыш.

Visual C++ 6.0, насколько помню, выделяемую такой конструкцией память не обнуляет. Для примера. В любом случае, если мы не надеемся на то, что у системы завалялись обнулённые страницы, это придётся делать нашему процессу, увы.


А если танцевать от хэш-таблицы? Функция h(x)=x%n, получаем n классов (некоторые из которых, возможно, пустые), оба дубликата в одном классе; время создания - O(n), среднее время проверки одного класса - O(1). Правда, при этом совершенно не используем ограниченность спектра значений.

eNoseпри иницилизации массива ничего физически не выделяется.
Я что-то пропустил?
После инициализации мы имеем адрес начала области памяти, к которой можно обращаться. Откуда она берётся, в таком случае?

NiticaAbstraction,

Массив в 500 элементов, а мы отжираем 2 Mb. Спорный выигрыш.

в формулировке задачи вроде как ясно сказано, что ограничений по памяти нет.
Ограничений нет. Но эти 500 1250 страниц кому-то надо выделить, а потом эти полмиллиона миллион с хвостиком машинных слов кому-то обнулить.

eNose,

Проверил на C#, проверил на C++.
Я прав ;)

eNose,

Где ж я вам его возьму?
Но вообще, идея выделять память только при обращении к ней подразумевает, что мы обращаемся не напрямую к памяти, а вызываем некоторый метод, который вначале проверяет, выделили ли нам эту память. Что выливается в потерю производительности.