Блог

Главная - Вопросы по программированию - Максимальное количество символов Python в строке?

Максимальное количество символов Python в строке?

#python

Вопрос:

Я пытаюсь найти максимальное количество символов в строке с помощью цикла. До сих пор это код, который я написал :-

 def max_char_count(string):
    max_char = ''
    max_count = 0
    for char in string:
        count = string.count(char)
        if count > max_count:
            max_count = count
            max_char = char
    return max_char

print(max_char_count('apple hellooo'))

Но проблема, с которой я сталкиваюсь, заключается в том, что есть 3 л и 3 о. Я получаю результат только в виде l. Как я могу настроить код, чтобы показать правильное количество символов? Спасибо.

Комментарии:

1. В случае ничьей вы хотите составить список всех персонажей, которые связаны по максимуму? Если это так, вам нужно сохранить список символов, а не один max_char .

2. @Samwise Да, это верно. Я хотел бы показать и то, и другое. Ну ладно. таким образом, max_char должен быть списком.

3. FWIW использовать гораздо более простой подход collections.Counter . c = collections.Counter("apple hellooo") ; print([k for k, v in c.items() if v == max(c.values())])

4. @Samwise, хотя и хороший подход. Я пытаюсь использовать чисто циклы и типы данных, а не модуль.

5. @Samwise также m = max(c.values()) , а затем используйте это в listcomp для O(n) вместо n^2

Ответ №1:

Ваш подход неэффективен, потому что вам нужно выполнить итерацию по всей строке для вычисления string.count(char) , в то время как вы все равно выполняете итерацию по всей строке, что дает временную сложность O(n^2)

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

 def max_char_count(string):
    ret = []
    counter = dict() # create an empty dict to store the character counts
    # Itrate over the string once to count the characters
    # N iterations
    for char in string:
        # `.get()` returns the given default value (0) if the `char` key doesn't exist
        # If it does, it returns the value for that key
        # Then you increment it
        counter[char] = counter.get(char, 0)   1 

    # Find the max value 
    # (another loop over the dict, worst-case N iterations)
    max_count = max(counter.values())    
    
    # Iterate over the dict one last time to get the keys that have a value == max_count
    # Again, worst-case N iterations
    for char, count in counter.items():
        if count == max_count:
            ret.append((char, count))

    return ret

Теперь, print(max_char_count('apple hellooo')) возвращается [('o', 3), ('l', 3)]

Если вы не хотите изобретать счетное колесо, используйте collections.Counter его вместо этого. counter = collections.Counter(string)

Поскольку у нас есть три цикла, и ни один из них не является вложенным циклом, мы получаем временную сложность O(3*n) (или просто O(n))

Комментарии:

1. Что делать, если строка string = 'apple is fruit but applepie is desert

Ответ №2:

Вы можете использовать словарь символов для подсчета вхождений, затем найти наибольшее количество и вернуть все ключи, которые имеют это количество. Конструктор fromkeys() позволит вам инициализировать количество букв до нуля, что значительно упростит цикл подсчета. Выбор букв с максимальным количеством можно выполнить с помощью понимания списка.

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

 string    = 'apple hellooo'

counts    = dict.fromkeys(string,0)  # initialize counts to zero
for c in string: counts[c]  = 1      # compute characters counts
max_count = max(counts.values())     # find maximum count
result    = [c for c,n in counts.items() if n==max_count] # matching characters

print(result)
['o', 'l']
Метки: