美文网首页
Leetcode_169_多数元素_hn

Leetcode_169_多数元素_hn

作者: 1只特立独行的猪 | 来源:发表于2020-03-13 20:48 被阅读0次

题目描述

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例

示例 1:

输入: [3,2,3]
输出: 3

示例2:

输入: [2,2,1,1,1,2,2]
输出: 2

解答方法

方法一:哈希表

思路

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = {}
        for num in nums:
            if num in dic:
                dic[num] += 1
            else:
                dic[num] = 1
        for i in dic:
            if dic[i] > len(nums) // 2:
                return i

时间复杂度

O(n)

空间复杂度

O(n)

方法二:摩尔投票法

思路

通过不断消除不同元素直到没有不同元素,剩下的元素就是我们要找的元素。
代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = 0
        for num in nums:
            if cnt == 0:
                res = num
            if res == num:
                cnt +=1
            else:
                cnt -= 1
        return res

时间复杂度

O(n)

空间复杂度

O(1)

相关文章

  • Leetcode_169_多数元素_hn

    题目描述 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素...

  • hn[0]hn

    hn[1]hn

  • 多数元素

    给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假...

  • 多数元素

    题目 难度级别:简单 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2...

  • 多数元素

    题目描述:给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素...

  • 多数元素

    题目: 题目的理解: 将数组排序,取中间值就是多数元素了。 python实现 提交 // END 有一种奇迹就是相信未来

  • 多数元素

    给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可...

  • 多数元素

    给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假...

  • 零基础学Web前端开发(2)

    今天回忆关于文字段落的标签写法, 标题标签: 文章中一级一级的标题都用标签表示...

  • 微信管理库

    数据库存储结构 微信(hn_nzwx_wx) 微信组(hn_nzwx_group) 日志表(hn_nzwx_log...

网友评论

      本文标题:Leetcode_169_多数元素_hn

      本文链接:https://www.haomeiwen.com/subject/rzlyshtx.html