Во многих проблемах кодирования, а также в повседневных задачах кодирования поиск количества элементов в списке — это то, с чем мы сталкиваемся довольно часто. Когда я впервые начал изучать 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), что делает нас (и интервьюеров) очень счастливыми :)
Оставайтесь с нами, чтобы узнать больше о программировании :)