我是靠谱客的博主 孝顺往事,最近开发中收集的这篇文章主要介绍剑指 Offer 39. 数组中出现次数超过一半的数字,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

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

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 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]

学习一下大佬的思路:

解题思路:

本文将 “数组中出现次数超过一半的数字” 简称为 “众数”
需要注意的是,数学中众数的定义为 “数组中出现次数最多的数字” ,与本文定义不同。

本题常见的三种解法:

  1. 哈希表统计法: 遍历数组 nums ,用 HashMap 统计各数字的数量,即可找出 众数 。此方法时间和空间复杂度均为 O ( N ) O(N) O(N)
  2. 数组排序法: 将数组 nums 排序,数组中点的元素 一定为众数。(我想起来的方法就是这个)
  3. 摩尔投票法: 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 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) (na) 个数字的 票数和一定仍 > 0 >0 >0 ,即后 ( n − a ) (n−a) (na) 个数字的 众数仍为 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 都可以 缩小剩余数组区间 。当遍历完成时,最后一轮假设的数字即为众数。

算法流程:

  1. 初始化: 票数统计 votes = 0 , 众数 x
  2. 循环: 遍历数组 nums 中的每个数字 num
    1. 当 票数 votes 等于 0 ,则假设当前数字 num 是众数;
    2. num = x 时,票数 votes 自增 1当 num != x 时,票数 votes 自减 1 ;
  3. 返回值: 返回 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. 数组中出现次数超过一半的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(45)

评论列表共有 0 条评论

立即
投稿
返回
顶部