Печать самого большого и второго по величине элемента в словаре

Я написал функцию, которая принимает строку в качестве входных данных и передает словарь, который указывает наиболее часто встречающиеся элементы / символы.

Часть 1 - Просто найти наиболее часто встречающегося персонажа

def mostoccur(arr):

   n = len(arr)
   dict={}

   # filling the dictionary with itesm and their frequency using dict.get()

   for i in range(n):
       dict[arr[i]] = dict.get(arr[i],0) + 1


   return dict


string = "aabbccdddddddd"

# turning the string into a list, so it's iterable

ls = list(string)
ans = mostoccur(ls)
print("The dictionary of all the characters and their frequency: \n",ans)

maximum = max(ans)
print("\nThe most occuring character is:",maximum)

Но затем мне стало любопытнее, и я захотел напечатать наиболее часто встречающийся и второй по частоте элемент в словаре. Таким образом, я написал примерно следующее:

Часть 2 - Хорошо, теперь давайте найдем второго наиболее часто встречающегося персонажа.

# defining a dictionary to store the most and second most occurring element

biggest = {'most-occuring':0, 'second-most-occuring':0}

# nested loops to go through all values in the dictionary

for a in ans.items():                                  # O(N)
   for b in ans.items():                               # O(N)
       if a < b:                                       
           a,b = b,a
           biggest['most-occuring'] = a
           biggest['second-most-occuring']= b

                                                       # Total = O(N^2)

print(biggest)

Большой O

Я написал большую букву «О» для каждой операции рядом с ней, и когда я смотрю на нее, мне действительно не нравится то, что я написал. Я имею в виду, что O (N ^ 2) звучит слишком дорого и неэффективно.

Не могли бы вы рассказать мне о лучших способах написания этого?

Please bear in mind that I'm not looking for a method that utilizes any libraries.

Как вы думаете, почему if a < b - это O (n)? Я вижу это как O (1).

jpp 10.08.2018 16:30

Это O(n**2), потому что a < b - это O(1). Решением O(n) было бы один раз перебрать список и отслеживать два самых высоких значения, которые вы видели. Также см. collections.Counter.most_common

Patrick Haugh 10.08.2018 16:31

Насколько я понимаю, «если» будет происходить для каждого цикла «цикла», и, следовательно, это (O (f (n) x g (n)), я ошибаюсь?

Pouya Ataei 10.08.2018 16:34
Подсчет повторяющихся символов в строке в Python может дать вам другой взгляд на то, как упростить ваш подход.
benvc 10.08.2018 16:37

@PatrickHaugh для присланной вами ссылки требуется библиотека. Мне нужно импортировать «Счетчик» из «коллекций», о которых я знал до публикации вопроса ...

Pouya Ataei 10.08.2018 16:48

@NeophytePolyhistor Я рекомендовал вам пойти и прочитать исходный код, чтобы увидеть, как реализован Counter.most_common, извините, если я не совсем понял.

Patrick Haugh 10.08.2018 16:50

@PatrickHaugh О, здорово, это хорошая идея!

Pouya Ataei 10.08.2018 16:50
1
7
85
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Используйте heapq.nlargest, например:

from collections import Counter
import heapq
string = "aabbccdddddddd"
counts = Counter(string)
heapq.nlargest(2, counts, key=lambda k: counts[k])

И без использования библиотек, если ваша функция возвращает то же самое, что и Counter:

keys = list(counts.keys())
keys.sort(key=lambda x: counts[x],reverse=True)
top_two = keys[:2] # just the keys
{ k : counts[k] for k in keys[:2] } # dict of top two

Никаких библиотек, никаких встроенных функций. Внимательно прочтите вопрос. Я знаю о счетчике.

Pouya Ataei 10.08.2018 16:51

Сожалею. Пропустил эту строчку. Добавление правки к моему ответу.

T Burgis 10.08.2018 17:02
Ответ принят как подходящий

Вот простой алгоритм, который делает это в O(n):

string = "aabbbccdddddddd"

def get_frequency(string):
    chars = {}
    for char in string:
        chars[char] = chars.get(char, 0) + 1 

    biggest = [None, 0]
    second = [None, 0]

    for entry in chars.items():
        char, count = entry
        if count > biggest[1]:
            second = biggest
            biggest = entry
        elif count > second[1]:
            second = entry

    return {
        "most-occurring": biggest[0],
        "second-most-occurring": second[0]
    }

print(get_frequency(string))

Это печатает {'second-most-occurring': 'b', 'most-occurring': 'd'}

Обратите внимание, что я добавил дополнительную букву «b» к string, чтобы сделать эту букву второй по частоте.

Вы могли бы сделать это более питоническим, объединив две строки в -> второй, самый большой = самый большой, запись

Pouya Ataei 11.08.2018 07:07

В целом, большое спасибо за решение. Мне это нравится :)

Pouya Ataei 11.08.2018 07:42

Привет, приятель, я был свидетелем того, что удаление «None» из массива приведет к ошибке! Не понимаю почему! не могли бы вы осветить меня?

Pouya Ataei 12.08.2018 08:40

Цикл for пытается получить доступ ко второму элементу (индекс 1) каждого массива, если вы удалите None, вы получите IndexError

TallChuck 13.08.2018 15:10

так почему бы нам по-прежнему не получить ошибку индекса после того, как мы выполнили цикл с одним элементом и получили доступ к индексу 0?

Pouya Ataei 13.08.2018 15:56

Другие вопросы по теме