Блог

Итак, вопрос таков: «Сумма раз, когда в списке есть дубликаты».

т. е. Если Ввод: 1 2 3 1 4 1 5 6 2 9 8

Затем вывод должен быть (5), так как 1-это три раза, а (2) — два раза в списке, и если в списке нет повторяющихся элементов. Код должен возвращать значение -1.

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

PS: Я впервые задаю здесь вопрос, так что, возможно, я совершил какую-то ошибку. Я был бы признателен, если бы вы могли заняться и этим тоже. Заранее спасибо.

 your_list = list(input().split())
dict_of_counts = {item:your_list.count(item) for item in your_list}
#print(dict_of_counts)
values = dict_of_counts.values()
k = list(values)
#print(k)
total = 0
j=[k[i] for i in range(0,len(k)) if k[i]>1]
y=[k[u] for u in range(0,len(k)) if k[u]<=1]
#print("j list is:" ,j)
#print("y list is:" ,y)
if len(y) == len(k):
     total = "-1"
for t in range(len(j)):
     total=total j[t]
print(total)
 

 your_list = input().split()
dict_of_counts = {}
for item in your_list:
    dict_of_counts[item] = dict_of_counts.get(item, 0)   1
total = sum(val for val in dict_of_counts.values() if val > 1)
if total == 0:
    print(-1)
else:
    print(total)
 

Или вы можете попробовать:

 your_list = input().split()
n = 0
for i in set(your_list):
    x = your_list.count(i)
    if x > 1:
        n  = x
if n == 0:
    print(-1)
else:
    print(n)
 

построение dict_of_count имеет сложность O(n^2), потому что вы подсчитываете числа для каждой позиции в списке. Вы могли бы немного уменьшить это, используя set(your_list) в понимании, но это все равно будет O(n^2) в худших сценариях.

Более эффективным подходом было бы использовать индексацию O(1) словаря для подсчета значений в цикле. Это то, что делает класс счетчика из коллекций:

 L = [1, 2, 3, 1, 4, 1, 5, 6, 2, 9, 8]
dupsum = sum(c for c in Counter(L).values() if c>1) or -1

print(dupsum) # 5
 

Если вам не разрешено использовать библиотеки, вы можете создать словарь вручную в цикле for:

 counts = dict()
for n in L: counts[n] = counts.get(n,0)   1
dupsum = sum(c for c in counts.values() if c>1) or -1
 

Эти решения приведут к результатам за O(n) времени вместо O(n^2)

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

 dups   = [n for s in [set()] for n in L if n in s or s.add(n)]
dupsum = len(dups) len(set(dups)) or -1