Найти пропущенные элементы последовательности

shl, 185 просмотров

-4

Дана последовательность целых чисел 0..N (N заранее неизвестно). В ней не хватает двух чисел - найти их. Причём, с минимальной возможной сложностью.

Для вида задачи с одним элементом сложность O(n) - просуммировать все числа последовательности и вычесть это из суммы ряда.
Для двух такое уже не прокатывает. Что ещё можно придумать?

Примечание:
2Uchozhor: последовательность не отсортирована, каждое значение встречается только один раз. Затраты памяти фиксированные, сложность должна быть линейная, по идее.

Примечание:
2Uchozor: получается, всё-таки надо сортировать?

Примечание:
crimaniak, круто, работает! Спасибо!

Ответы:

Uchozhor

Как то не однозначно определено условие.

Kandasoft

Все, извиняюсь.
Ищу решение

Uchozhor

Трудно понять, но может быть следующий алгоритм:
проверять Аn=[А(n-1)+А(n+1)]/2, гда Аn - n-ый член (отранжированной) последовательности. Должно получиться 2 несоответствия. Отказ, если искомые отсутствующие члены последовательности расположены по краям.

Есть еще стопроцентный вариант, ставить быстро устаревающую куку при посещении страниц сайта и отдачу картинок производить при ее наличии

Для двух чисел пробегись по массиву, накапливая сумму и произведение. В конце останется решить уравнение X1+X2=a; X1X2=b; Где а=сумма полного ряда - сумма де-факто и b=произведение полного ряда / произведение де-факто.

14 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.