查找奇数次出现的数字的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

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