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

读前福利

问题描述

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

示例:

输入:[1,2,3,2,2,2,5,4,2]

输出:2

分析问题

哈希表法

我们最容易想到的方法就是使用哈希表法,去统计每个数字出现的次数,即可很容易的求出众数。

def majorityElement(nums):
    #用字典来保存每个数字出现的次数
    data_count = {}
    for x in nums:
        if x in data_count:
            data_count[x] = data_count[x] + 1
        else:
            data_count[x] = 1
    max_value=0
    max_key=0
    #遍历字典,取出次数最大的
    #因为题目说给定的数组一定存在众数
    #所以最大的次数就是众数
    for key in data_count:
        value=data_count[key]
        if value>max_value:
            max_value=value
            max_key=key
    return max_key

data=[1,2,3,2,2,2,5,4,2]
print(majorityElement(data))

该算法的时间复杂度是O(n),空间复杂度也是O(n)。

排序算法

我们将数组进行排序,那排序后的数组的中点一定就是众数。

def majorityElement(nums):
        #将数组排序
        nums.sort()
        #返回排序数组中的中点
        return nums[len(nums) // 2]

data=[1,2,3,2,2,2,5,4,2]
print(majorityElement(data))

Boyer-Moore 投票算法

这道题最经典的解法是Boyer-Moore 投票算法。Boyer-Moore 投票算法的核心思想是票数正负抵消,即遇到众数时,我们把票数+1,遇到非众数时,我们把票数-1,则所有的票数和一定是大于0的。

我们假设数组nums的众数是x,数组的长度为n。我们可以很容易的知道,若数组的前a个数字的票数和为0,那么剩余n-a个数字的票数和一定是大于0的,即后n-a个数字的众数仍然为x。

我们记数组的首个元素是n1,数组的众数是x,遍历并统计票数。当发生票数和为0时,数组剩余元素的众数一定也是x,这是因为:

  1. 当n1等于x时,抵消的所有数字中,有一半是众数x。
  2. 当n1不等于x时,抵消的所有数字中,众数的个人最少为0,最多为一半。

所以,我们在去掉m个字符里,最多只去掉了一半的众数,所以在剩余的n-m个元素中,x仍然为众数。利用这个特性,在每次遇到票数和为0时,我们都可以缩小剩余数组区间。当遍历完成时,最后一轮假设的数字即为众数。

class Solution:
    def majorityElement(self, nums):
        #票数和
        counts=0
        for num in nums:
            #如果票数和为0,我们假设num元素为众数
            if counts == 0:
                x = num
            #如果是众数票数+1,否则票数-1
            if num==x:
                counts=counts+1
            else:
                counts=counts-1
        return x

该算法的时间复杂度是O(n),空间复杂度是O(1)。

最后

送大家几本比较不错的算法书籍~

小争哥数据结构与算法
链接:https://pan.baidu.com/s/19Jk_G_-QTnGb3GRyzbENgA

密码:keis

谷歌大佬LeetCode刷题指南
链接:https://pan.baidu.com/s/1vtRIsVltTxmIioqqkeSS5g

密码:r3xg

算法小抄
链接:https://pan.baidu.com/s/1rU_T6GRZ-WmV9QFmnJfCBg

密码:unh5

更多有趣内容,请扫码关注一波~

原文链接:,转发请注明来源!