美文网首页
每日一题20201106(169. 多数元素)

每日一题20201106(169. 多数元素)

作者: 米洛丶 | 来源:发表于2020-11-06 11:05 被阅读0次
image.png

hash表

1. 思路很简单,先遍历数组,存储每个元素的个数
2. 遍历hash表,拿到大于 n/2的数字,直接return
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        hash = dict()
        for n in nums:
            if n not in hash:
                hash[n] = 1
            else:
                hash[n] += 1
        for k, v in hash.items():
            if v > len(nums) / 2:
                return k
        return -1

时间复杂度: O(N)
空间复杂度: O(N)

投票算法

思路很简单,假设你是秦始皇,数组里面有很多其他国家,你们秦兵遇到自己人就+1,遇到其他人就-1,如果你超过了所有国家一半的兵力,那么最后活下来的肯定就是你的士兵。这里之所以能这么确定,是因为题目强调了一定存在多数元素!

代码思路是,开始遍历数组,如果当前的士兵数量是0,则把当前士兵设置为遍历到的元素,比如: 秦

接下来如果遇到秦,则count+1, 遇到的是赵或者其他士兵,则秦和赵士兵同归于尽。下一轮遍历,由于秦的count是0了,则将当前士兵设置为遍历到的士兵。
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return -1
        # 当前士兵数量
        count = 0
        # 当前士兵
        current = None
        for n in nums:
            if count == 0:
                current = n
            count += 1 if n == current else -1
        return current

时间复杂度: O(N)
空间复杂度: O(1)

相关文章

  • 每日一题20201106(169. 多数元素)

    hash表 时间复杂度: O(N)空间复杂度: O(N) 投票算法 时间复杂度: O(N)空间复杂度: O(1)

  • [Leetcode] 169. 多数元素

    169. 多数元素 来源: 169. 多数元素 1. 解题思路 因为多数元素出现次数大于 ⌊ n/2 ⌋, 所以...

  • LeetCode-169-多数元素

    LeetCode-169-多数元素 169. 多数元素[https://leetcode-cn.com/probl...

  • 169. 多数元素

    169. 多数元素 经典面试题 摩尔投票法

  • 169. 多数元素

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

  • 169.多数元素

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

  • 169.多数元素

    解题思路 解法一:排序法 如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序,那么下标为 ⌊n/2...

  • 169. 多数元素

    解法 神奇的解法,因为要返回的数,要超过半数,所以相同加1,不同减1,最终count应该是大于0的,所以可以这样去...

  • 169.多数元素

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

  • TOP 100 57 - 64

    169. 多数元素[https://leetcode-cn.com/problems/majority-eleme...

网友评论

      本文标题:每日一题20201106(169. 多数元素)

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