хитрая проблема со связанным списком - PullRequest
Новая
       15

хитрая проблема со связанным списком

8 голосов
/ 21 марта 2011

Дано три списка: A, B и C длиной n каждый. если любые 3 три числа (по 1 из каждого списка), сумма до нуля возвращает true. Я хочу решить эту проблему с o (n) сложностью. Я отсортировал списки, и я могу подумать о создании любой хэш-карты с суммой 2 связанные списки или сравнение трех списков вместе [o (n * n * n)]. Предложите несколько способов импровизировать методы, чтобы уменьшить сложность. Я не могу думать ни о каком ... Спасибо в adv

Ответы [ 3 ]

7 голосов
/ 21 марта 2011

Списки отсортированы, верно? Создайте отсортированный массив C ' из C за O ( n ).

Для каждой из n ² пар x , y in A × B , проверьте, - ( x + y ) в C ' с двоичным поиском. Общая сложность времени O ( n ² lg n ), сложность пространства O ( n ).

Создание хеш-таблицы из C еще больше снижает сложность времени до O ( n ²), за счет веры в хеш-таблицы O (1).

5 голосов
/ 21 марта 2011

Я не думаю, что это возможно в o(n²) (т. Е. Действительно лучше , чем n²), но это можно сделать в O(n²) (т. Е. Как n²) следующим образом:

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

Мы можем сделать это следующим образом (код Python): 

def getIndicesFromTwoArrays(A,B,t):
    a,b=0,0
    while(A[a]+B[b]!=t):
        b=b+1
        if b==len(B):
            return (-1,-1)
        if A[a]+B[b]<t:
            a=a+1
            b=b-1
            if a==len(A):
                return (-1,-1)
    return (a,b)

Время выполнения вышеперечисленного составляет O(n).Требуемое дополнительное пространство составляет O(1), поскольку нам нужно хранить только два указателя.Обратите внимание, что вышеприведенное можно легко преобразовать так, чтобы оно работало с двусвязными списками.

Тогда, в общем, нам просто нужно сделать следующее: 

def test(A,B,C):
    B.reverse()
    for c in C:
        if getIndicesFromTwoArrays(A, B, c) != (-1,-1):
            return True
    return False

Это приводит к продолжительности работы O(n²) и дополнительное пространство O(1).

0 голосов
/ 21 марта 2011

Вы не можете сделать это со сложностью O (n), поскольку это NP-полная проблема (если P = NP). Посетите Вики-страницу о проблеме подмножества для возможных решений.

...