当前位置：网站首页>面试题 17.10. 主要元素

面试题 17.10. 主要元素

2022-04-23 15:58:00 【张.Joshua】

面试题 17.10. 主要元素

题号：力扣面试题 17.10
知识点：数组，计数
目标完成度：24/150
总结
题干：

思路：

1.本题难点在于时间复杂度为O(N)，空间复杂度为O(1)的要求。使用摩尔投票法
2.摩尔投票法：

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        ans = 0
        for num in nums:
            if count==0:
                ans = num
            if ans == num:
                count += 1
            if ans != num:
                count -= 1
        if nums.count(ans) > len(nums)//2:
            return ans
        else:
            return -1

版权声明
本文为[张.Joshua]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_44742084/article/details/124362770

边栏推荐

猜你喜欢

随机推荐