查找数组中出现奇数次的那个数字

  有一个数组,其中的数都是以偶数次的形式出现,只有一个数出现的次数为奇数次,要求找出这个出现次数为奇数次的数。

集合+统计

解题思路

  最简单能想到的,效率不高。利用集合的特性,通过 Python 的 set() 函数筛选出数组中有哪些数,然后遍历集合,使用 List 的 count 方法统计集合中每个元素在数组中出现的次数,如果是奇数次则直接返回该数。

Python 实现
1
2
3
4
5
def find_odd_times_num(arr):
num = set(arr)
for i in num:
if arr.count(i) % 2 != 0:
return i

排序+遍历

解题思路

  将数组从小到大排序,然后遍历数组,并对出现的数进行计数b,当出现不同的数时,判断上一个数出现次数是奇数还是偶数。

Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
def find_odd_times_num(arr):
arr.sort()
cnt = 1
for i in range(1, len(arr)):
if arr[i] != arr[i - 1]:
if cnt % 2 != 0:
return arr[i-1]
else:
cnt = 1
else:
cnt += 1
if cnt % 2 != 0:
return arr[i]

  改进版本:

  借用计数排序的思想,先找到数组中最大的元素,然后开辟一个新数组,原数组中每个元素的值即为新数组的下标,遍历原数组记录每个元素出现的次数,最后遍历新数组,找到奇数,返回其下标。

1
2
3
4
5
6
7
8
def find_odd_times_num(arr):
m = max(arr)
cnt = [0] * m
for i in arr:
cnt[i-1] += 1
for j in range(m):
if cnt[j] % 2 != 0:
return j+1

Map + 统计

解题思路

  遍历数组记录出现次数先计数,并存储到 Map 中,再遍历 Map,找出 Map 中 value 为奇数的 key。

Python 实现
1
2
3
4
5
6
7
8
9
10
def find_odd_times_num(arr):
dict = {}
for i in arr:
if i in dict:
dict[i] += 1
else:
dict[i] = 1
for k, v in dict.items():
if v % 2 != 0:
return k

位运算

解题思路

  巧妙地采用异或的特点进行处理,即整数 n 与 0 的异或结果为 n,整数 n 与 n 的异或结果为 0,异或运算满足交换律和结合律。即,所有出现偶数次的数异或的结果为 0,而对于出现次数为奇数次n的数,其出现的前 n-1 次异或的结果为 0,而 0 与其最后1次出现进行异或,得到该数本身。因此,可以很方便找出出现次数为奇数次的数。

Python 实现
1
2
3
4
5
def find_odd_times_num(arr):
res = 0
for i in arr:
res ^= i
return res
坚持原创技术分享,您的支持将鼓励我继续创作!