Найти пары в массив целых чисел, сумма которых равна n (бонус: сделать это в линейном времени)


Я отдал этому выстрел, и код работает. Я на правильном пути? Как код может быть улучшен? Кроме того, я не знаю как определить, если это будет линейное время или нет. Может кто-то может нарушить это определение для меня?

'''
Problem statement: Find pairs in an integer array whose sum is equal to n (bonus: do it in linear time)

@author: Anonymous3.1415
'''

def pair_sum_to_n(integer_list, n):
    pairs = []
    #checks for the occurence of halfs
    if not n % 2:
        if integer_list.count(n/2) > 1:
            pairs.append((n/2, n/2))
        integer_set = set(integer_list) - {n/2}
    #finds pairs of integers where x + (n - x) = n
    for x in integer_set:
        if (n - x) in integer_set:
            if (n - x, x) not in pairs:
                pairs.append((x, n - x))
    return pairs

integer_list = list(map(int, raw_input().strip().split(" ")))
pairs = pair_sum_to_n(integer_list, 10)
print(pairs)


300
2
задан 28 января 2018 в 05:01 Источник Поделиться
Комментарии
2 ответа

Определение проблемы

она не имеет четко определенных ли pair_sum_to_n([1, 9, 9, 1, 9], 10) влечет за собой. ваша реализация предполагает {(1, 9)} в качестве желаемого результата. другие возможности включают в себя


  • {(1, 9)}

  • {(9, 1)}

  • {(9, 1), (1, 9)}

  • [(1, 9), (1, 9)]

  • [(1, 9), (9, 1)]

  • [(9, 1), (1, 9)]

  • [(1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9)]

  • ...

Вмятие

integer_set не определяется для нечетных n

Особый случай обращения n/2даже n

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

Параметр name integer_list

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

Повторяемое копию установить

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

1
ответ дан 29 января 2018 в 07:01 Источник Поделиться

В map по умолчанию возвращает список. Вам не нужна еще одна обертка вокруг него.

Ваша текущая реализация имеет \$ o(п^2) \$ сложность. Заявление:

(n - x, x) not in pairs

это из \$ О(П) \$ времени, который находится внутри цикла с \$ О(П) \$.

Чтобы сделать это в линейном времени, генерировать словарь/хэш, где вы храните просто \$ н - х \$ значения в первой итерации. Во втором (и независимая) итерации, просто добавьте пару $$ \влево( мин(х,\ п - х),\ макс(х,\ п - х) \право) $$ для каждого x в вашем списке, если \$ о(1) \$ подстановки в dict-это правда.

2
ответ дан 28 января 2018 в 11:01 Источник Поделиться