Skip to content

169 majority element

169. Majority Element

题目: https://leetcode.com/problems/majority-element/

难度: Easy

思路：

其实这个我有点有想到过

给定一个长度为 n的数组,其中有一个数，它出现的次数大于⎣n/2⎦，称为主要元素，找到它.

这个很像之前做过的一道CLRS的题目，想法可以用divide & conquer.

  • 如果数组长度 <= 2,那么return第一个即解决问题
  • 如果长度 > 2，那么可以两两配对，对于配对一样的结果，删去
    • 如果最后余一个，这一个留下
    • shuffle之后再尝试两两配对，直到最后结果不再改变

这样肯定是能解决问题的，因为为了满足次数大于⎣n/2⎦这个条件。


     1 2        1 2          1 2         1 2
     2 3        2 3          2 3         2 3
     2          4 2          2 2         2 3
                2             4 2        3 3
                                          3 2
                                          2 2
                                          2 2

思路容易implement非常难啊.

这个问题有一个很出名的算法

Boyer-Moore众数(majority number) 问题

在数组中找到两个不相同的元素并删除它们，不断重复此过程，直到数组中元素都相同，那么剩下的元素就是主要元素。

这个算法的妙处在于不直接删除数组中的元素，而是利用一个计数变量.

伪码

def majorityElement(self, nums):
    count,major=0,0
    for n in nums:
        if count==0:
            major=n
        if major==n:
            count+=1
        else:
            count-=1
    return major
回到顶部