主要元素（超过一半元素）

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5

示例 2：

输入：[3,2]
输出：-1

示例 3：

输入：[2,2,1,1,1,2,2]
输出：2

示例代码1（投票算法）：

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

解题思路 超过半数和不超过半数的值最大的区别是什么?

当我们扫描一遍下来的时候，直接进行一个只要两个不同就可以消除的消消乐，如果有超过半数的值，那么剩下的这个值必然是它。 这是因为其他值总共也没有这个值的人数多，所以不管怎么消除，这个值都会留下来。 (注意: 只有超过半数才一定会最终留下来，连等于半数都不一定是最终留下来的结果。而即使小于等于半数的留下来，也无法通过第二轮验证)

全部消除后count为0，即可以两两消除，必然不存在超过半数的值，不用进行第二轮验证。

第二轮验证:

原数组没有超过半数的值的时候，也可能有剩下的值。 比如说 [1,2,3],在消除过后仍然可以得到3。 所以还需要遍历一遍统计上轮发现的值的个数，确保它是超过半数的。

复杂度分析

• 时间复杂度：O(N)O(N)，其中 N 为数组长度
• 空间复杂度：O(1)O(1)

示例代码2：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        x = len(nums) // 2
        return -1 if nums.count(nums[x])