Leetcode_169 Majority Element

发表于 | 分类于

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且数组中的众数永远存在。

“””
摩尔投票：

每次从序列里选择两个不相同的数字删除掉（或称为“抵消”）
最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

“””

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0

        for i in range(len(nums)):
            if count == 0:
                record = nums[i]
                count += 1
            elif record == nums[i]:
                count += 1
            else:
                count -= 1
        return record