@Relocatik

Как разработать алгоритм для нахождения двух элементов, сумма которых дает x?

5d2c7f89c1387354247204.png
Помогите решить данную задачу, ничего не приходит в голову
  • Вопрос задан
  • 184 просмотра
Решения вопроса 1
@Karpion
Сначала упорядочим множество (массив) S по возрастанию.
Затем берём два крайних элемента, считаем их сумму. Допустим, сумма больше, чем нужно - тогда отбрасываем правый (самый большой) элемент; а если меньше - то самый левый (ну, не отбрасываем - а сдвигаем указатель к центру массива). И повторяем - пока не получится нужная сумма или пока элементы не закончатся.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 3
Zoominger
@Zoominger
System Integrator
На фриланс, там "помогут".
Ответ написан
Комментировать
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Фантастический способ:
Изучить O-нотацию.
Изучить различные алгоритмы с их оценкой сложности в O-нотации.
Подобрать необходимые алгоритмы и провести их композицию в свой алгоритм, решающий задачу.

Реальный способ:
Бегать по всем форумам с просьбой помочь, авось кто и откликнется.

P.S. Задача, кстати, примитивная, в два действия, первое O(n log n), второе O(n).
Ответ написан
@pulk
В условии ничего не сказано про использование дополнительной памяти, поэтому можно ее решить за O(N).
hashtable = {}
for x in X:
y = S - x
if y in hashtable:
return x, y
hashtable[x] = 0
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы