Есть массив целых чисел и число N. Найти два элемента массива, сумма которых равна N (или установить, что такой пары не существует). Допускается модификация массива.

Здравствуйте, conraddk, Вы писали:

C>Есть массив целых чисел и число N. Найти два элемента массива, сумма которых равна N (или установить, что такой пары не существует). Допускается модификация массива.

Первое что пришло в голову:
первый элемент заменяем на N-mas[0], для всех остальных выполняем сравнение mas[i] и всех предыдущих элементов. Если есть такой же, то нашли, если нет, тозаменяем mas[i] на N-mas[i]. Если дошли до конца, то нет такой пары. В принципе можно не проводить сразу поиск а рассмотреть битовое поле размера N , для определения вхождения mas[i] в предыдущую последователность, а потом уже делать поиск.

conraddk,

Сортируем массивчик, потом проходом в противоположных направлениях устанавливаем существование. O(n*log(n)).

Здравствуйте, andrey.def, Вы писали:

AD>Первое что пришло в голову:
AD>первый элемент заменяем на N-mas[0], для всех остальных выполняем сравнение mas[i] и всех предыдущих элементов. Если есть такой же, то нашли, если нет, тозаменяем mas[i] на N-mas[i]. Если дошли до конца, то нет такой пары.
Если я все правильно понял, то алгоритм квадратичный — в общем-то, разницы с перебором всех возможных пар нету. Рядом уже написали O(n log n).

Здравствуйте, conraddk, Вы писали:

C>Здравствуйте, andrey.def, Вы писали:

AD>>Первое что пришло в голову:
AD>>первый элемент заменяем на N-mas[0], для всех остальных выполняем сравнение mas[i] и всех предыдущих элементов. Если есть такой же, то нашли, если нет, тозаменяем mas[i] на N-mas[i]. Если дошли до конца, то нет такой пары.
C>Если я все правильно понял, то алгоритм квадратичный — в общем-то, разницы с перебором всех возможных пар нету. Рядом уже написали O(n log n).

Ну вообще-то разница есть. Потому как я ж писал, что можнои не проводить поиск во всём префиксе, а сначала определить вхождение в битовое поле, например, что будет быстрее.
А O(n log n) это только сортировка, а как же дальнейший поиск? не имеет никакой сложности? Здаётся мне, что тут ещё n нужно добавить.

насчёт битового поля конечноже приврал — забыл про целые числа, это подходит только для натуральных. Для целых можно попробовать хэш сочинить
В худшем случае мой подход требует n*n. а сортировка с поиском n*n*log, ИМХО

AD>А O(n log n) это только сортировка, а как же дальнейший поиск? не имеет никакой сложности? Здаётся мне, что тут ещё n нужно добавить.

O(n*log n)+O(n*log n)=O(n*log n)


Дальнейший перебор делается с помощью бинарного поиска...

P.S. хакерское решение — так как "модифицировать массив можно",
берём и делаем array[2]=N-array[1] всё, нужные элементы есть

Здравствуйте, andrey.def, Вы писали:

AD>В худшем случае мой подход требует n*n. а сортировка с поиском n*n*log, ИМХО
Не, неправильное ХО.
Сортировка с последующим поиском — О(n*log(n) + n) = O(n*log(n)) Собственно, задача как раз про этот поиск — как его сделать за O(n). Но у Lazy Cjow Rhrr в ответе есть ключевое слово, поэтому решение зачтено

Что касается битового поля — а если числа повторяются, и сумму как раз надо составлять из одинаковых (см. сабж)?

Здравствуйте, e-Xecutor, Вы писали:


AD>>А O(n log n) это только сортировка, а как же дальнейший поиск? не имеет никакой сложности? Здаётся мне, что тут ещё n нужно добавить.

EX>O(n*log n)+O(n*log n)=O(n*log n)

Согласен, совсем дурак стал

Здравствуйте, conraddk, Вы писали:

C>Что касается битового поля — а если числа повторяются, и сумму как раз надо составлять из одинаковых (см. сабж)?

Не , ну тут-то как раз всё пучком Ещё раз внятно опишу...
до mas[i] мы заменяем все элементы на N-mas[j], и по префиксу состоящего из N-mas[j] делаем поле. => при наличии там элемента mas[i] мы узнаём, что существует пара, дающая в сумме N, после этого уже выполняем поиск конкретного места...
Нсчёт эффективной реализации битового поля нужно подумать — опыта у меня не много, но если в доп массиве записывать мин адреса для всех вхождений в поле тогда и доп поиск не нужно будет делать.
PS: может я и не прав. Остаётся только понять где

Здравствуйте, e-Xecutor, Вы писали:

EX>O(n*log n)+O(n*log n)=O(n*log n)
EX>

EX>Дальнейший перебор делается с помощью бинарного поиска...
Можно обойтись и без бинарного поиска.

EX>P.S. хакерское решение — так как "модифицировать массив можно",
EX>берём и делаем array[2]=N-array[1] всё, нужные элементы есть

Здравствуйте, e-Xecutor, Вы писали:


AD>>А O(n log n) это только сортировка, а как же дальнейший поиск? не имеет никакой сложности? Здаётся мне, что тут ещё n нужно добавить.

EX>O(n*log n)+O(n*log n)=O(n*log n)
EX>

EX>Дальнейший перебор делается с помощью бинарного поиска...

Не нужно никакого бинарного поиска. Берется два "указателя", первый изначально указывает на первый элемент последовательности, второй на последний,
если сумма этих двух элементов больше N, то сдвигаем вправо первый,
если меньше, то сдвигаем влево второй,
если равны, то нашли пару.

Сложность O(n)

Здравствуйте, conraddk, Вы писали:

C>Есть массив целых чисел и число N. Найти два элемента массива, сумма которых равна N (или установить, что такой пары не существует). Допускается модификация массива.

1. Делаем, как уже описали. O(n*logn)

2. Можем использовать O(N) памяти и все числа >= 0 (если это не так, то сначала прибавляем к каждому числу минимальное из чисел и в качестве N рассматриваем N+2*Amin).

Заводим массив Cnt[0..N] (обнуленный).
Для каждого числа из массива:
если число Ai <= N, то делаем Cnt[Ai] = Cnt[Ai]+1; (достаточно хранить 0,1 или 2)

a. n < N. Еще раз просматриваем массив, и для каждого Ai, проверяем есть ли N-Ai в массиве. Сложность O(n).
б. n > N. Просматриваем массив cnt, для i элемента проверяем есть ли элемент N-i. Сложность O(N).
Таким образом получаем сложность O(n)+O(min(n,N)).

Здравствуйте, conraddk, Вы писали:

C>Есть массив целых чисел и число N. Найти два элемента массива, сумма которых равна N (или установить, что такой пары не существует). Допускается модификация массива.

Если множество допустимых значений чисел в массиве ограничено, то существует алгоритм O(n), но требующий памяти столько же сколько и мощность этого множества.

пусть исходный массив — x[0..k], его элементы лежат в пределах: a <= xi <= b

Алгоритм: создаем новый массив в котором роль индекса будут играть числа из множества, а роль элемента — индекс этого числа в исходном массиве — массив m[a..b].

Далее перебираем исходный массив x, если x[i], такое, что x[i] + m[x[i]] == N, то выходим, иначе записываем m[x[i]] = i.

Если такое xi найдено, то искомая пара чисел x[i] и x[m[x[i]]]

Здравствуйте, Serpenter, Вы писали:

S>Здравствуйте, conraddk, Вы писали:

C>>Есть массив целых чисел и число N. Найти два элемента массива, сумма которых равна N (или установить, что такой пары не существует). Допускается модификация массива.

S>Если множество допустимых значений чисел в массиве ограничено, то существует алгоритм O(n), но требующий памяти столько же сколько и мощность этого множества.

S>пусть исходный массив — x[0..k], его элементы лежат в пределах: a <= xi <= b

S>Алгоритм: создаем новый массив в котором роль индекса будут играть числа из множества, а роль элемента — индекс этого числа в исходном массиве — массив m[a..b].

S>Далее перебираем исходный массив x, если x[i], такое, что x[i] + m[x[i]] == N, то выходим, иначе записываем m[x[i]] = i.

Вот тут вот какая-то ошибка. С чего вдруг исходное число + его индекс должны равняться N и почему это будет ответом. Может x[i]+x[m[N-x[i]]] == N ?

S>Если такое xi найдено, то искомая пара чисел x[i] и x[m[x[i]]]

А вообще в предыдущем посте я уже довольно подробно описал этот способ.

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, Serpenter, Вы писали:

S>>Здравствуйте, conraddk, Вы писали:

C>>>Есть массив целых чисел и число N. Найти два элемента массива, сумма которых равна N (или установить, что такой пары не существует). Допускается модификация массива.

S>>Если множество допустимых значений чисел в массиве ограничено, то существует алгоритм O(n), но требующий памяти столько же сколько и мощность этого множества.

S>>пусть исходный массив — x[0..k], его элементы лежат в пределах: a <= xi <= b

S>>Алгоритм: создаем новый массив в котором роль индекса будут играть числа из множества, а роль элемента — индекс этого числа в исходном массиве — массив m[a..b].

S>>Далее перебираем исходный массив x, если x[i], такое, что x[i] + m[x[i]] == N, то выходим, иначе записываем m[x[i]] = i.

_DA>Вот тут вот какая-то ошибка. С чего вдруг исходное число + его индекс должны равняться N и почему это будет ответом. Может x[i]+x[m[N-x[i]]] == N ?
а ну да, но в общем идея ясна


S>>Если такое xi найдено, то искомая пара чисел x[i] и x[m[x[i]]]

_DA>А вообще в предыдущем посте я уже довольно подробно описал этот способ.
не читал