查找奇数次出现的数字的Python程序

本文概述

• Python3
• 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

Python3

# Python program to find the element occurring
# odd number of times
      
# function to find the element occurring odd
# number of times
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
      
      
# driver code 
arr = [ 2 , 3 , 5 , 4 , 5 , 2 , 4 , 3 , 5 , 2 , 4 , 4 , 2 ]
n = len (arr)
print (getOddOccurrence(arr, n))
  
# This code has been contributed by 
# Smitha Dinesh Semwal

输出如下：

5

一种更好的解决方案是使用哈希。使用数组元素作为键, 并将其计数作为值。创建一个空的哈希表。一对一遍历给定的数组元素并存储计数。该解决方案的时间复杂度为O(n)。但是它需要额外的空间来进行哈希处理。

程序：

python

# Python program to find the element occurring odd number of times
  
def getOddOccurrence(arr):
  
     # Initialize result
     res = 0
      
     # Traverse the array
     for element in arr:
         # XOR with the result
         res = res ^ element
  
     return res
  
# Test array
arr = [ 2 , 3 , 5 , 4 , 5 , 2 , 4 , 3 , 5 , 2 , 4 , 4 , 2 ]
  
print "% d" % getOddOccurrence(arr)

输出如下：

5

请参考完整的文章查找出现次数的奇数更多细节！