找出数组中出现次数超过一半的数

  数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

计数+比较

  不考虑效率,采用最简单的办法,遍历数组,使用 List 的 count() 方法统计元素出现的次数:

1
2
3
4
5
6
def more_than_half_num(arr):
half = len(arr) // 2
for i in arr:
if arr.count(i) > half:
return i
return None

  构造一个map,key为元素的值,value为元素出现的次数,然后遍历map找到目标元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
def more_than_half_num(arr):
dict = {}
for i in arr:
if i in dict:
dict[i] += 1
else:
dict[i] = 1
half = len(arr) // 2
for k, v in dict.items():
if v > half:
return k
return None

排序+中位数

  数组排序后,如果符合条件的数存在,则一定是数组中间那个数。可使用排序算法对数组进行排序,然后求排序后数组的中间数 + 判断中间数出现次数是否超过数组的一半。下面以快速排序为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def part_sort(arr, left, right):
key = right
while left < right:
while left < right and arr[left] <= arr[key]:
left += 1
while left < right and arr[right] >= arr[key]:
right -= 1
arr[left], arr[right] = arr[right], arr[left]
print(arr)
arr[left], arr[key] = arr[key], arr[left]
return left
def quick_sort(arr, left, right):
if left >= right:
return
index = part_sort(arr, left, right)
quick_sort(arr, left, index - 1)
quick_sort(arr, index, right)
def more_than_half_num(arr):
length = len(arr)
quick_sort(arr, 0, length - 1)
res = arr[length // 2]
if arr.count(res) > length // 2:
return res
else:
return None

一次遍历

  数组中有一个数字出现的次数超过数组长度的一半,也就是说出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候利用两个辅助变量,一个记录数字出现的次数,一个记录数字。

  • 当我们遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加1;
  • 如果下一个数字和我们之前保存的数字不同,则次数减1。
  • 如果次数为零,我们需要保存下一个数字,并把次数设为1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def more_than_half_num(arr):
res = arr[0]
cnt = 1
for i in range(1, len(arr)):
if arr[i] == res:
cnt += 1
else:
cnt -= 1
if cnt == 0:
res = arr[i]
cnt = 1
if arr.count(res) > len(arr)//2:
return res
else:
return None
坚持原创技术分享,您的支持将鼓励我继续创作!