首页 > itarticle > leetcode-169题:majority element

leetcode-169题:majority element

admin 11月 11, 2020 0

题目：Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

思路：已知这样的主元素存在，那么根据它的定义可知，这个数字的数量一定比其他数字的数量和大。因此若每次删除两个不相等的数字，那么最后剩下的数字即为所求。

代码：

def majorityElement(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if nums == None:
        return None
    num = None
    counter = 0
    for n in nums:
        if counter == 0:
            counter = 1
            num = n
        elif n == num:
            counter += 1
        else:
            counter -= 1
    return num