Понимание списка Python с несколькими списками и if else conditon

Question

Я хотел бы перебрать два одинаково длинных набора и определить, находятся ли элементы в каждом наборе также в массиве.

Это вопрос Hackerrank, о котором я уже решил. Тем не менее, я использую Hackerrank для дальнейшего понимания Python. Я узнал о понимании списков, и пока я верю, что пытаюсь использовать его, чтобы считаться плохим производственным кодом. Мне все же хотелось бы изучить возможности синтаксиса языка для моих собственных знаний.

Это код, который устанавливает его:

n, m = map(int, input().split()) 
arr = list(map(int, input().split())) 
A = set(map(int, input().split())) 
B = set(map(int, input().split())) 

Задача состоит в том, чтобы выводить целое число со значением +1 для каждого элемента, как в А и обр и -1 для каждого элемента, как в B и обр.

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

3 2 
1 5 3 
3 1 
5 7 

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

1 

Это обеспечивает достижение требуемых результатов:

print(sum([1 for a in A if a in arr]) + sum([-1 for b in B if b in arr])) 

Однако, это ближе к тому, что я хотел бы достичь:

sum([1 if a in arr else -1 if b in arr for a, b in zip(A, B)]) 

EDIT (это ближе на самом деле):

print(sum(1 if a in arr -1 if b in arr for a, b in zip(A, B))) 

Как вы можете видеть оба однострочечники, так что не о попытке сократить код, а просто понять возможности списка понимания и вещей кода , Если это невозможно или даже плохая практика, мне тоже очень интересно.

Это ссылка Hackerrank: https://www.hackerrank.com/challenges/no-idea

Answer 1

Прежде всего, отказаться от списка понимания; кормить значения непосредственно в sum() с выражением генератора:

sum(1 for a in A if a in arr) 

Если A является установить, использовать set.intersection() method, чтобы извлечь общие ценности, то взять длину результата:

len(A.intersection(arr))) 

Это быстрее, чем попытка тестирования arr для каждого значения. Это делает, но сначала создайте новый объект set(), но вы создавали список раньше, так что это не так.

В этот момент она гораздо проще просто вычесть вторую длину:

len(A.intersection(arr)) - len(B.intersection(arr)) 

Вы можете избежать создания наборов вообще обернув над arr и тестирование каждого значения в arr против любого A или B; это тоже быстрее, потому что статус набора тесты являются O (1) постоянное время:

sum(1 if v in A else -1 if v in B else 0 for v in arr) 

Вашего метода тестирования a in arr для каждого значения в наборе A, требует полного список проверить arr, если значение a не настоящее время; это приводит к тестированию членства перед списком линейной проблемы времени O (N), и вы делаете это для каждого значения в Aи для каждого значения в B, так что вы заканчиваете с O ((A + B) * N) = = O (KN). Тестирование каждого значения в arr против множества - это только O (N * 1) == O (N) время.

Кроме того, если значения в arrне являются уникальными, ваш подход фактически приведет к неправильному ответу; вы считаете только счастливые или несчастливые цифры один раз, в то время как проблема требует от них подсчета каждый раз, когда они появляются.

Answer 2

Как насчет coverting массива, чтобы установить и с пересечением

s = set(arr) 
print(len(A.intersection(s)) - len(B.intersection(s))) 

Edit: Это решение не будет работать для повторяющихся значений в arr

Answer 3

Ваше решение является большим, но вот загвоздка. Вы используете структуру данных set для двух наборов чисел и list для вашего массива. При применении оператора in над списком вы выполняете поиск O (n), тогда как в наборе такая же операция O (logn) (В среднем случае python есть O (1)!). Таким образом, ваша общая временная сложность равна O (2 * m * n) = O (m * n). Вы можете искать в обратном порядке, такие как:

For each element in array, if element in A then +1, if element in B then -1.

Общая сложность этого будет O (N * 2 * logm) = О (п * logm)

Подробнее о времени сложности питона here

Answer 4

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

n, m = map(int, input().split()) 
arr = list(input().split()) 
A, B = set(input().split()), set(input().split()) 
print(sum([(e in A) - (e in B) for e in arr])) 

Answer 5

Наиболее эффективный способ решения этой проблемы, вероятно, поставить пункты A и B в словарь (в качестве ключей), причем значения являются 1 или -1 в зависимости от того, какой набор они пришли.Это позволит вам просканировать список arr и легко получить значение для добавления к сумме:

ab_dict = {a: 1 for a in A} 
ab_dict.update((b, -1) for b in B) 

result = sum(ab_dict.get(x, 0) for x in arr) 

Расчет результата имеет ту же вычислительную сложность, используя несколько условных операторов в выражении генератора (sum(1 if x in A else -1 if x in b else 0 for x in arr)) , но должен быть быстрее на каком-то постоянном множителе, так как для каждого элемента есть только один поиск по запросу вместо двух тестов на членство в наборе.