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

本文概述

Python3
python

给定一个正整数数组。所有数字均出现偶数次, 只有一个数字出现奇数次。在O(n)时间和恒定空间中找到数字。
例子：

Input : arr = {1, 2, 3, 2, 3, 1, 3} Output : 3Input : 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 + = 1if (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

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

输出如下：