Найти все пары чисел, сумма которых меньше S - PullRequest
5 голосов
/ 11 апреля 2011

Для отсортированного массива a [0 ... n-1] найти все пары чисел, сумма которых меньше S. Есть ли решение O (n)?

Ответы [ 5 ]

4 голосов
/ 11 апреля 2011

Ты сейчас на собеседовании? Они скоро вернутся в комнату?

Поскольку он отсортирован, то одним из решений (если оно есть!) Является [0] и некоторое наибольшее [M]. Затем обработайте нижний индекс вверх от 0, а верхний индекс - вниз от M. И некоторые детали о том, что нужно поднять и когда отклонить.

Редактировать - поскольку все еще может быть O (n ^ 2) решений (например, если S больше чем в два раза больше самой большой записи), трюк будет в выражении решений диапазоны. В противном случае, просто перечисление займет слишком много времени.

0 голосов
/ 11 апреля 2011

Нет решения O (n).Например, если у вас есть такой список: 1,2,3,4 ... n и S = ​​3 * n, то сумма каждой пары меньше S. И количество пар, которые должны быть возвращены, равно n * (n-1) / 2.

0 голосов
/ 11 апреля 2011

Перечисление всех таких пар уже содержится в O (n ^ 2) (обратите внимание, что это отличается от задачи суммирования с точностью до S, поскольку в этом случае перечисление может быть выполнено в O (n), например пара времен (w, x), 1 пара времени (y, z), ... "

0 голосов
/ 11 апреля 2011

Решение Дэвида должно работать. Это будет O (N), даже если существует более N решений.

1) Начните с * ptr1 = a [0] и * ptr2 = a [X] <= S (X не всегда N-1) </p>

2) Переместить ptr2 назад, пока ptr1 + ptr2 <= S. </p>

- на данный момент ptr1 + все индексы до ptr2 являются решениями.

3) Переместить ptr2 назад на один индекс и переместить ptr1 вверх на один индекс

- повторить

Продолжить до ptr1> ptr2

0 голосов
/ 11 апреля 2011
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...