Алгоритм Python для сравнения двух отсортированных списков и подсчета количества одинаковых элементов - PullRequest
Новая
       20

Алгоритм Python для сравнения двух отсортированных списков и подсчета количества одинаковых элементов

0 голосов
/ 08 мая 2018

Мне нужно разработать алгоритм, который сравнивает два отсортированных списка одинаковой длины и возвращает количество общих значений между ними.

Так что, если у меня есть два списка a = [2, 9, 15, 27, 36, 40] и b = [9, 11, 15, 23, 36, 44], алгоритм должен вернуть значение 3 как 9, 15 и 36 присутствуют в обоих списках.

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

В моем текущем коде используется любой алгоритм слияния массивов, который на данный момент не работает, так как я все еще не уверен относительно r1 и r2, хотя я думаю, что они были бы наиболее правым элементом в массиве, но я не знаю, как получить это. например. r1 = 40 (из списка a) и r2 = 44 (из списка b)? 

global a
a = [2, 9, 15, 27, 36, 40]

global b
b = [9, 11, 15, 23, 36, 44]

global c
c = []

def merge (a1, a, r1, a2, b, r2, c, list3):
    i = a
    j = b
    k = c
    r1 = 
    r2 = 
    while i <= r1 and j <= r2:
        if a1[i]<=a2[j]:
            a3[k] = a1[i]
            i += 1
        elif a3[k] >= a2[j]:
            j += 1
            k += 1
    while i <= r1:  
        a3[k] = a1[i]
        i += 1
        k += 1 
    while j <= r2:  
        a3[k] = a2[j]
        j += 1
        k += 1

Спасибо за помощь и отзывы.

Ответы [ 3 ]

0 голосов
/ 08 мая 2018

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

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

Алгоритм:

  • Пусть i и j будут индексами a1 и a2, соответственно инициализированными в 0
  • Если a1[i] < a2[j], мы знаем, что a1[i] не существует в a2, поскольку i и j указывают на наименьший элемент в соответствующих массивах. Итак, мы продвигаемся i вперед.
  • То же самое с a2[j] < a1[i].
  • Если a1[i] == a2[j], то мы нашли общий элемент и продвигаемся на i и j на 1 и продолжаем до конца любого из массивов.

код 

def find_common(a1, a2):
    list_len = len(a1)
    a3 = []
    i = j = 0
    while i < list_len and j < list_len:
        if a1[i] < a2[j]:
            i += 1
        elif a2[j] < a1[i]:
            j += 1
        else:
            a3.append(a1[i])    
            i +=1
            j +=1
    return a3

a = [2, 9, 15, 27, 36, 40]
b = [9, 11, 15, 23, 36, 44]
print(find_common(a, b))
0 голосов
/ 08 мая 2018

Используя хеш-таблицу, вы можете решить это за линейное время.

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

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

Чтобы избежать подсчета дубликатов, во время итерации проверяйте, является ли предыдущий элемент тем же, и в этом случае переходите к следующему элементу. Вам понадобится дополнительная переменная, чтобы отслеживать предыдущий элемент.

0 голосов
/ 08 мая 2018

r1 и r2 являются длинами двух списков.
Простое объединение двух списков не так сложно, как в вашем примере, вот упрощенное объединение: 

def merge(a1, a2):
    r1, r2 = len(a1), len(a2)
    a3 = []
    i = j = 0

    while i < r1 and j < r2:
        if a1[i] < a2[j]:
            a3.append(a1[i])
            i += 1
        else:
            a3.append(a2[j])
            j += 1

    while i < r1:
        a3.append(a1[i])
        i += 1
    while j < r2:
        a3.append(a2[j])
        j += 1

    return a3

In []:
a = [2, 9, 15, 27, 36, 40]
b = [9, 11, 15, 23, 36, 44]
merge(a, b)

Out[]:
[2, 9, 9, 11, 15, 15, 23, 27, 36, 36, 40, 44]

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

...