JZ39 数组中出现次数超过一半的数字

发表于 分类于 本文字数： 339 阅读时长 ≈ 1 分钟

JZ39 数组中出现次数超过一半的数字

描述

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

例如输入一个长度为9的数组$[1,2,3,2,2,2,5,4,2]$。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：$n≤50000$，数组中元素的值 $0≤val≤10000$

要求：空间复杂度：$O(1)$，时间复杂度 $O(n)$

输入描述：

保证数组输入非空，且保证有解

示例1

1
2
输入：[1,2,3,2,2,2,5,4,2]
返回值：2

示例2

1
2
输入：[3,3,3,3,2,2,2]
返回值：3

示例3

1
2
输入：[1]
返回值：1

题解

首先是直接创建字典，存每一个数字出现的频率，超过一半时直接返回，或者排序后找中间的数字(一定有解)。

官方给出了一个候选人法：

1
2
既然一定有解，那么众数一定大于数组长度的一半。
所以有核心思想：若两个数不等，则消去这两个数，最终留下的一定是众数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        cond = -1
        con = 0
        for num in numbers:
            if con == 0 :
                cond = num
                con += 1
                continue
            if num != cond:
                con -=1
                continue
            con +=1
        return cond