概述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
我做这个题想的就比较简单,排个序,然后取中间位置的数字就一定是多数存在的元素
class Solution:
def majorityElement(self, nums: List[int]) -> int:
flag = int(len(nums)/2)
nums.sort()
pre = set(nums[:flag+1])
last = set(nums[flag:len(nums)])
result = pre & last
return list(result)[0]
学习一下大佬的思路:
解题思路:
本文将 “数组中出现次数超过一半的数字” 简称为 “众数” 。
需要注意的是,数学中众数的定义为 “数组中出现次数最多的数字” ,与本文定义不同。
本题常见的三种解法:
- 哈希表统计法: 遍历数组
nums
,用 HashMap 统计各数字的数量,即可找出 众数 。此方法时间和空间复杂度均为 O ( N ) O(N) O(N) 。 - 数组排序法: 将数组
nums
排序,数组中点的元素 一定为众数。(我想起来的方法就是这个) - 摩尔投票法: 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O ( N ) O(N) O(N) 和 O ( 1 ) O(1) O(1) ,为本题的最佳解法。
方法一: 哈希表统计法
class Solution:
def majorityElement(self, nums: List[int]) -> int:
mode_dic = {}
for num in nums:
if num in mode_dic.keys():
mode_dic[num] += 1
else:
mode_dic[num] = 1
res = 0
most_time = 1
for key in mode_dic.keys():
if mode_dic[key] >= most_time:
most_time = mode_dic[key]
res = key
return res
方法三: 摩尔投票法
设输入数组
nums
的众数为 x x x ,数组长度为 n n n 。
推论一: 若记 众数 的票数为 + 1 +1 +1 ,非众数 的票数为 − 1 −1 −1 ,则一定有所有数字的 票数和 > 0 >0 >0 。
推论二: 若数组的前 a a a 个数字的 票数和 = 0 =0 =0 ,则 数组剩余 ( n − a ) (n-a) (n−a) 个数字的 票数和一定仍 > 0 >0 >0 ,即后 ( n − a ) (n−a) (n−a) 个数字的 众数仍为 x x x 。
根据以上推论,记数组首个元素为 n 1 n_1 n1 ,众数为 x x x ,遍历并统计票数。当发生 票数和 = 0 =0 =0 时,剩余数组的众数一定不变 ,这是由于:
- 当 n 1 = x n_1 = x n1=x: 抵消的所有数字,有一半是众数 x x x 。
- 当 n 1 ≠ x n_1 neq x n1=x: 抵消的所有数字,众数 x x x 的数量为一半或 0 个。
利用此特性,每轮假设发生 票数和 = 0 =0 =0 都可以 缩小剩余数组区间 。当遍历完成时,最后一轮假设的数字即为众数。
算法流程:
- 初始化: 票数统计
votes = 0
, 众数x
; - 循环: 遍历数组
nums
中的每个数字num
;- 当 票数
votes
等于0
,则假设当前数字num
是众数; - 当
num = x
时,票数votes
自增1
;当 num != x
时,票数votes
自减 1 ;
- 当 票数
- 返回值: 返回
x
即可;
class Solution:
def majorityElement(self, nums: List[int]) -> int:
res = 0
votes = 0
for num in nums:
if votes == 0:
res = num
if res == num:
votes += 1
else:
votes -= 1
return res
这个方法,我跪了,真的
最后
以上就是孝顺往事为你收集整理的剑指 Offer 39. 数组中出现次数超过一半的数字的全部内容,希望文章能够帮你解决剑指 Offer 39. 数组中出现次数超过一半的数字所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复