Алгоритм поиска пар в массиве без перебора всех пар?

Question

[therea19]

Существует ли алгоритм поиска пар чисел в массиве, различающихся ровно на 1, без перебора всех возможных пар в массиве.
После написания программы с перебором всех пар время работы > 1 секунды, а нужно < 1 секунды
P.s. важно, что если одно число уже состоится в какой-то паре, то в другой быть не может
P.p.s писал на Python, может проблема в этом? Переписать на си? Или бессмысленно?

Answer 1

[Руслан .]

Можно отсортировать массив и потом за один проход найти все пары.
Например так:

src = [1, 5, 9, 11, 10, 4]
src.sort()
[print('{0:d} - {1:d}'.format(src[i], src[i + 1])) for i in range(len(src)-1) if src[i + 1] - src[i] == 1]

Результат:
4 - 5
9 - 10
10 - 11

По сложности это лучше полного перебора.
Сортировка на месте - O(N*log(N))
Проход по списку еще O(N).
Т.е. в целом O(N*(1 + log(N)))
В случае полного перебора O(N*N)

Но тут есть дублирование, число 10 входит в 2 пары, как его исключить и какую пару оставить решайте сами.

Comments

[Игорь Статкевич]

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

Answer 2

[Игорь Статкевич]

Если чего то не существует, надо придумать, или подождать пока другие придумают ) не перебирая как узнать отличаются ли они на единицу ? (тут встречный вопрос: чисел стоящих на своих местах в массиве, или вообще всех чисел)

Comments

[Игорь Статкевич]

Если всех чисел, то сортировка и вперед

Answer 3

[Иван Мельников]

Покажите свой код.
Требуется найти разбиение с наибольшим количеством пар?
Дело в том, что разные разбиения дают разное кол-во пар.
Например, у массива [1, 2, 3, 4] существует два разбиения: {(2, 3)} и {(1, 2), (3, 4)}.
Вот пример решения (сложность O(N*log N)):

def pairs(src):
    i = 0
    src.sort()
    result = list()    
    while i + 1 < len(src):
        if src[i+1] - src[i] == 1:
            result.append((src[i], src[i+1]))
            src = src[:i] + src[i+2:]
            i = max(0, i-1)
        else:
            i += 1
    return result

src1 = [1, 5, 9, 11, 10, 4]
src2 = []
src3 = [1, 5, 2, 9, 1, 1, 4, 2, 2, 2]
print(src1, pairs(src1))
print(src2, pairs(src2))
print(src3, pairs(src3))

ps. Обращаю внимание, что функция меняет список!

Answer 4

[Andrey Dugin]

import numpy as np

N = 20
numbers = np.random.randint(0, 40, N)
print('Исходный массив:', *numbers)
print('Уникальные пары: ', end='')
numbers.sort()
cache = set()
for index in np.argwhere(np.diff(numbers) == 1):
    pair = numbers[index.item():][:2]
    if cache.isdisjoint(pair):
        cache.update(pair)
        print(*pair, sep='-', end=' ')

Исходный массив: 28 10 24 19 17 0 20 24 5 30 26 39 6 38 31 39 28 25 18 24
Уникальные пары: 5-6 17-18 19-20 24-25 30-31 38-39

Необходимо доработать алгоритм отсева повторов в соответствии с замечанием от Иван Мельников