Рубрики

Программа Python, чтобы найти число, происходящее нечетное количество раз

Дан массив натуральных чисел. Все числа встречаются четное число раз, кроме одного числа, которое встречается нечетное количество раз. Найдите число в O (n) времени и постоянном пространстве.

Примеры :

Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3

Input : arr = {5, 7, 2, 7, 5, 2, 5}
Output : 5

# 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 = [2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2 ]

n = len(arr)

print(getOddOccurrence(arr, n))

  
# Этот код был добавлен
# Смита Динеш Семвал

Выход:

5

Лучшее решение — использовать хеширование. Используйте элементы массива в качестве ключа и их количество в качестве значения. Создайте пустую хеш-таблицу. Один за другим пересекают заданные элементы массива и сохраняют счетчики. Временная сложность этого решения составляет O (n). Но это требует дополнительного места для хеширования.

Программа:

питон

      
# Программа Python для поиска элемента, встречающегося нечетное количество раз

  

def getOddOccurrence(arr):

  

    # Инициализировать результат

    res = 0

      

    # Обойти массив

    for element in arr:

        # XOR с результатом

        res = res ^ element

  

    return res

  
# Тестовый массив

arr = [ 2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2]

  

print "% d" % getOddOccurrence(arr)

Выход:

5

Пожалуйста, обратитесь к полной статье о поиске числа, встречающегося с нечетным числом раз, чтобы получить более подробную информацию!

Рекомендуемые посты:

Программа Python, чтобы найти число, происходящее нечетное количество раз

0.00 (0%) 0 votes