Напишите функцию для возврата первого элемента, который появляется нечетное число раз в строке

ProgramBox

Напишите функцию для возврата первого элемента, который появляется нечетное число раз в строке

Post author:admin
Запись опубликована:3 декабря, 2022
Post category:Вопросы по программированию

#python

Вопрос:

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

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

 def getOddOccurrence(arr, arr_size): 
    for i in range(0,arr_size): 
        count = 0
        for j in range(0, arr_size): 
            if arr[i] == arr[j]: 
                count =1
              
        if (count % 2 != 0): 
            return arr[i] 
          
    return -1

код драйвера:

 arr = ["Hello world!"] 
n = len(arr) 
print(getOddOccurrence(arr, n))
# Output: "Hello world!

Если заданная строка "Hello world!" , как мне вернуть первый элемент, который появляется нечетное число раз?

1. нечетное количество раз сбивает с толку. Можете ли вы поделиться тем, для чего вы хотите получить результат "Hello world!" ?

2. Во-первых, зачем вы передаете список, если вы просто хотите проверить одну строку? В настоящее время вы не сравниваете какие-либо символы этой строки, только элементы в списке

3. "Hello World" -> "H" "llo World" -> "l" Это тот результат, который вы ожидаете?

4. Когда вы запускаете оба цикла от 0 до n, вы ошибочно считаете элемент, который появляется с тем же индексом.

5. Да, я бы ожидал, что в этом случае H .

Ответ №1:

Поскольку было некоторое обсуждение, чтобы предоставить оптимизированное решение, вот оно: эта сборка основана на коде @SowjanyaRBhat и оптимизирует его. В значительной степени то, о чем упоминал @OneCriketeer.

Сложность пространства: O (N)
Сложность времени: O (N)

Подход 1: без collections.Counter

 from collections import defaultdict


def getOddOccurrence(myString):
    count = defaultdict(int)
    for letter in myString:
        count[letter]  = 1
    for letter in myString:
        if count[letter] % 2 != 0:
            return letter

Подход 2: с collections.Counter

(проверьте классную однострочную строку в @Alain .Ответ T)

 from collections import Counter


def getOddOccurrence(myString):
    count = Counter(myString)
    for letter in myString:
        if count[letter] % 2 != 0:
            return letter


# driver code
myString = "llo world!"
print(getOddOccurrence(myString))

# Output: "l"

1. Первые 3 строки функции можно заменить на count = collections.Counter(myString) …

2. Большое спасибо! Чтобы я правильно понял, использование функции dictionary похоже на хеширование? Затем он возвращается назад, чтобы найти первую нечетную встречающуюся букву? Спасибо всем за то, что так быстро отреагировали — не ожидал этого! 🙂

3. ДА. Это двухпроходное решение. В первом цикле мы используем dictionary для поддержания количества символов; во втором цикле мы проверяем наличие первого символа с нечетным числом.

4. Спасибо за разъяснение — только что узнал о хешировании сегодня, так что приятно видеть это на практике вот так 🙂

Ответ №2:

Возвращает первый элемент, имеющий нечетное число вхождений :

 def getOddOccurrence(myString):
    for letter in myString:
        letter_count = myString.count(letter)
        if letter_count%2 != 0:
            return letter
    return None
      
      
# driver code  
myString = "Hello world!"
print(getOddOccurrence(myString))

Вывод: «H»

1. Более оптимальным решением было бы избежать использования .count в цикле

2. я не знаю, как это сделать xD

3. Отлично! Большое вам спасибо! 🙂

4. удалена вторая строка

5. Выполните цикл по строке один раз. Поместите количество символов в словарь. Дважды выполните цикл по строке, затем верните первое значение dict с нечетным числом. O (N) решение, а не это O (N ^ 2)

Ответ №3:

Вы можете использовать счетчик из коллекций, чтобы получить количество символов, а затем просто найти первый символ с нечетным количеством:

 from collections import Counter
def firstOdd(S):
    return next((c for counts in [Counter(S)] for c in S if counts[c]%2),"")

print(firstOdd("Hello World")) # 'H'

print(firstOdd("bold World Wide Web")) # 'd'