leetcode-169 多数元素

98 阅读 0 评论 65 点赞

我是靠谱客的博主柔弱黑猫，这篇文章主要介绍leetcode-169 多数元素，现在分享给大家，希望可以做个参考。

https://leetcode-cn.com/problems/majority-element/submissions/

问题描述参考上方链接

学到了一种新算法Boyer-Moore 投票算法，这种算法对于多数元素这个问题解决得非常完美，不知道它还可以在哪些问题上应用。。。

思想：寻找数组中超过一半的数字，这意味着数组中其他数字出现次数的总和都是比不上这个数字出现的次数。即如果把该众数记为 +1 ，把其他数记为 −1 ，将它们全部加起来，和是大于 0 的。应用变量candidate记录当前众数候选，count记录次数，遍历数组，如果x==candidate->count+=1 否则 count-=1。如果count==0 时，改变candidate为当前元素x。

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    '''
    这是用set方法解决的 自己写的 o(n) o(n)
    def majorityElement(self, nums: List[int]) -> int:
        num = int(len(nums)/2)
        s = dict()
        for i in nums:
            if i not in s.keys():
                s[i] = 1
                continue
            s[i]+=1
        
        for k,v in s.items():
            if v>num:
                return k
        return -1
    '''
    # o(n)时间复杂度 o(1) 空间复杂度
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None
        
        for num in nums:
            if count ==0 :
                candidate = num
            count+=(1 if num==candidate else -1)
            
        return candidate
    #还有一种排序法，将数组排序后，返回nums[n//2]这个元素，因为在多数元素一定存在的前提下，num[n//2]一定是多数元素。具体解释可以看上方链接leetcode的题解

注意：以上这段代码只能在数组中一定存在超过一半数字时，此时的candidate就是目标值，如果前提是不确定的，那么，还需要验证candidate值出现的次数有没有超过一半数字，没有的话，就不存在target。也就是说Boyer-Moore 投票法得到的candidate可能是target，也可能不是，target要么不存在要么就是candidate

详情可见这一题https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey