Алгоритм, который проверяет, являются ли в массивах S и T целые числа s и t, поэтому s + t = k, если k задано число

Question

Я пытаюсь создать алгоритм, который принимает два массива, S и T из n целых чисел и целого числа k.Алгоритм проверяет, имеют ли массивы целые числа s и t, поэтому s + t = k. (S в S и t в T). Предполагается, что алгоритм имеет время выполнения O (n log n).

Попытался придумать что-то, что сортирует массив T и использует цикл for для прохождения через S и использует бинарный поиск, чтобы увидеть, найду ли я целое число, подобное k - S [i], для каждого элемента в S.у меня всегда есть время выполнения больше, чем n log n, я думаю.

Не ищу кого-то, чтобы написать код.Только спрашиваю здесь, чтобы получить некоторые идеи.

Answer 1

Сортировка двух списков, это O (n log n).

Затем настройте два итератора.Один итератор начинается с наименьшего значения в S и проходит через постоянно увеличивающиеся значения в S. Другой итератор начинается с наивысшего значения в T и выполняет итерацию по постоянно убывающим значениям.

Повторите следующее:

• , если текущие значения суммируются с числом, большим k , продвиньте T-итератор.Это должно уменьшить сумму.
• , если текущие значения суммируются с числом, меньшим k , продвиньте итератор S.Это должно увеличить сумму.
• , если текущие значения суммируются до k , а затем выйти с успехом.

Эта вторая фаза должна вызывать самое большее 2Nавансы, и, следовательно, O (n).Таким образом, общая сложность составляет O (n log n).

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

Answer 2

Сортировка оба массивы. Пройдите через них в противоположных направлениях. Если сумма двух элементов меньше, чем k, передвиньте «увеличивающийся» указатель, если он больше, чем k, пошагово уменьшающий указатель. Этот метод может быть немного медленнее, чем сортировка только одного из массивов, но последний проход определенно быстрее. И, вероятно, короче, потому что голова и хвостовая часть двух массивов могут быть пропущены (удалены).

Answer 3

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

• Сортировка одного из массивов (O (n log n))
• Для каждого элемента другого массива: (O (n) итераций)
  • Выполните двоичный поиск, чтобы увидеть, находится ли дополнительный элемент в другом массиве (O (log n) time)

Первый шаг занимает время O (n log n), а второй шаг состоит из O (n) итераций алгоритма O (log n), который, таким образом, также занимает время O (n log n). Поскольку O (n log n) + O (n log n) = O (n log n), ваш алгоритм выполняется за время O (n log n). Похоже, у вас есть именно тот алгоритм, который вы ищете!

Надеюсь, это поможет!

Answer 4

Сортировка O (n log n). Затем для каждого O (n) первых элементов у вас есть O (log n) поиск подходящего элемента. Это звучит как O (n log n) в целом (поскольку O (f) + O (f) = O (f) для любой функции f).

Answer 5

Ваш подход кажется правильным;сначала сортировка массивов, две операции O (n log n), а затем вы выполняете n двоичных поисков, каждый из которых O (log n).

Answer 6

Еще один метод: сохранить один из массивов в хеш-таблице (O (N)).Сделайте линейный проход через другой (O (N)) и для каждого элемента выполните поиск k-elem в хеш-таблице.Общее время выполнения: 2 * O (N): = O (N).Прибыль!