Учитывая два списка строк, как я могу сопоставить их так, чтобы как можно больше идентичных? - PullRequest
Новая
       21

Учитывая два списка строк, как я могу сопоставить их так, чтобы как можно больше идентичных?

1 голос
/ 20 февраля 2020

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

Пример ввода: 

list_1 = ['correct', 'wronganswer', 'correct', 'correct', 'timelimit']
list_2 = ['wronganswer', 'correct', 'timelimit', 'correct', 'timelimit'],

Пример вывода: 

4

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

result = 0
for el in list_1:
    if el in list_2:
        result += 1
        list_2.remove(el)
print(result)

result = 0
for el in set(list_1):
    result += min(list_1.count(el), list_2.count(el))
print(result)

Есть предложения о том, как сократить время обработки?

Ответы [ 4 ]

2 голосов
/ 20 февраля 2020

Попробуйте:

на основе словаря, и ключи снова сравниваются со следующими n входными значениями и значения уменьшаются, если ключи найдены и добавлены к результату вывода s

n = int(input())

d={}
for _ in range(n):
   x = input()
   try:
       d[x] +=1
   except KeyError:
       d[x] = 1

s=0   
for _ in range(n):

    x=input()

    try:
        if d[x] != 0:
            s+=1
            d[x] -= 1

    except KeyError:
        pass
print(s)
2 голосов
/ 20 февраля 2020

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

data = """5
correct
wronganswer
correct
correct
timelimit
wronganswer
correct
timelimit
correct
timelimit"""

lines         = data.split("\n")
count         = int(lines[0])
DOMResults    = lines[1:count+1]
KattisResults = lines[count+1:]

from collections import Counter
DOMCounts    = Counter(DOMResults)
KattisCounts = Counter(KattisResults)
matches = sum(min(KattisCounts[r],c) for r,c in DOMCounts.items())
print("matches:",matches)

# matches: 4
1 голос
/ 20 февраля 2020

Уже есть много хороших ответов, но вот мой поворот с использованием defaultdict. 

from collections import defaultdict

data = [5,
        'correct',
        'wronganswer',
        'correct',
        'correct',
        'timelimit',
        'wronganswer',
        'correct',
        'timelimit',
        'correct',
        'timelimit']

instances = data[0]
dom = defaultdict(int)

for entry in data[instances + 1:]:
    dom[entry] += 1

pairs = 0
for entry in data[1:instances + 1]:
    if dom[entry]:
        dom[entry] -= 1
        pairs += 1

print(pairs)
0 голосов
/ 20 февраля 2020

@ Ален опередил меня, но действительно, Counter был и моим решением: 

import sys
from collections import Counter

count = 0
counter_a = Counter()
counter_b = Counter()
for i, line in enumerate(sys.stdin):
    line = line.strip()
    if not i:
        count = int(line)
        continue
    if i > count:
        counter_b[line] += 1
    else:
        counter_a[line] += 1

result = 0
for line, counter_a_count in counter_a.items():
    if line in counter_b:
        result += min(counter_a_count, counter_b[line])

print(result)

Я верю, что его тоже будет быстрее, но это было "достаточно быстро":)

...