Во многих проблемах кодирования, а также в повседневных задачах кодирования поиск количества элементов в списке — это то, с чем мы сталкиваемся довольно часто. Когда я впервые начал изучать Python/программирование, я делал это так:

mylist = [1,1,1,1,2,3,3,3,3,4,4,4,4,4,4,5,5,5,7,7,7,8,8,8,8,8,8,8,9,9,9]
#Get unique elements of list
uniques = set(mylist)
#Store counts of elements in key-value pairs in python dictionary
element_counts = {}
#Iterate over set containing unique elements
for num in uniques:
#Assign count of each num as value
  element_counts[num] = mylist.count(num)
print(element_counts)

{1: 4, 2: 1, 3: 4, 4: 6, 5: 3, 7: 3, 8: 7, 9: 3}

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

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

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

mylist = [1,1,1,1,2,3,3,3,3,4,4,4,4,4,4,5,5,5,7,7,7,8,8,8,8,8,8,8,9,9,9]
#Store counts of elements in key-value pairs in python dictionary
element_counts = {}
#Iterate over list
for num in mylist:
#Checks if number exists in dictionary and if not, assigns a value of 1 to it.
  if num not in element_counts:
    element_counts[num] = 1
#If number already exists in dictionary, existing count is incremented by 1.
  else:
    element_counts[num] += 1
print(element_counts)

{1: 4, 2: 1, 3: 4, 4: 6, 5: 3, 7: 3, 8: 7, 9: 3}

Глядя на приведенный выше код, мы видим, что он выполняет именно то, что нам нужно. Теперь давайте посмотрим на временную сложность. Он выполняет одну итерацию по всем элементам в списке, что дает нам временную сложность O(n), где n — количество элементов в списке. Затем код просматривает словарь, чтобы узнать, содержит ли он текущий элемент. Словарь python на самом деле представляет собой хеш-карту, а это означает, что в большинстве ситуаций (за исключением действительно дрянного алгоритма хеширования и частых коллизий) средняя временная сложность для доступа/поиска по словарю составляет O (1). В результате общая временная сложность приведенного выше кода составляет O(n*1), что упрощается до O(n), что делает нас (и интервьюеров) очень счастливыми :)

Оставайтесь с нами, чтобы узнать больше о программировании :)