Пары с конкретными разница в Python


Дан массив arr различных целых чисел и неотрицательное целое число kнапишите функцию findPairsWithGivenDifference, которая возвращает массив всех парах [x,y] в Арр, такой, что x - y = k. Если не существует таких пар, возвращать пустую массив.

В решении, постарайтесь уменьшить использование памяти при сохранении эффективность времени. Докажите правильность своего решения и анализировать его время и пространство сложности.

Примечание: порядок пар в выходной массив должен поддерживать порядок y элемента в исходном массиве.

Примеры:

вход: arr = [0, -1, -2, 2, 1], k = 1 output: [[1, 0], [0, -1], [-1, -2], [2, 1]]

вход: arr = [1, 7, 5, 3, 32, 17, 12], k = 17

выход: []

Ограничения:

[срок] 5000 мс

[вход] массива.число Арр

0 ≤ обр. длина ≤ 100 [ввод]целое число k

к ≥ 0 [выход] массива.массив.целое число

def find_pairs_with_given_difference(arr, k):
    numbers = set()
    output = []
    # insert arr element into set
    for i in range(len(arr)):
        numbers.add(arr[i])

    # loop through the entire array
    for i in range(len(arr)):
        difference = arr[i]
        if difference - k in numbers:
            output.append([difference,(difference - k)])
    return output

Test case #1
Input: [4,1], 3
Expected: [[4,1]]
Actual: [[4, 1]]


Test Case #2
Input: [1,5,11,7], 4
Expected: [[5,1],[11,7]]


185
1
задан 15 марта 2018 в 10:03 Источник Поделиться
Комментарии
3 ответа

Код в посте (и в WolframH ответ) есть ошибка:

>>> find_pairs_with_given_difference([1], 0)
[[1, 1]]

Нет пары пунктов [1, 1] во входном массиве.

1
ответ дан 16 марта 2018 в 11:03 Источник Поделиться

Если массив больше, я это слово впервые отсортировать список кортежей (item, original_position)и тогда для каждого элемента, начать повторять вперед, пока порог k передается

sorted_items = [(item, pos) for pos, item in sorted(enumerate(arr), key=lambda x: x[1])]


[(-2, 2), (-1, 1), (0, 0), (1, 4), (2, 3)]

def find_pairs(sorted_items):
for i, (y, pos) in enumerate(sorted_items):
for x, pos2 in takewhile(lambda x: x[0] - y <= k, sorted_items[i+1:]):
if x - y == k:
yield pos, [x, y]


[(2, [-1, -2]), (1, [0, -1]), (0, [1, 0]), (4, [2, 1])]

list(pair for _, pair in sorted(find_pairs(sorted_items)))


[[1, 0], [0, -1], [-1, -2], [2, 1]]

Таким образом, вы устраните квадратичный рост итераций

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

Набор numbers могут быть созданы непосредственно из Iterable, в этом случае

numbers = set(arr)

Пройдемся по пунктам arrне показатели:

for y in arr:
if y - k in numbers:
output.append([y, y - k])

Или использовать список понимание, которое больше или меньше сделал для этого:

output = [[y, y - k] for y in arr if y - k in numbers]

Сложите все вместе и ваша функция будет очень короткий и четкий:

def find_pairs_with_given_difference(arr, k):
numbers = set(arr)
return [[y, y - k] for y in arr if y - k in numbers]

0
ответ дан 15 марта 2018 в 11:03 Источник Поделиться