多数元素

1. 题目描述

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

2. 示例

示例1

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

示例2

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

进阶
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

3. 解题

投票法：
定义数组元素的“票”只能投给数组元素值本身，每个数组元素一票
数组长度为n，若某一元素出现次数大于n/2，则其票数必定大于其他所有票数之和。
每次遍历到数组值nums[i]：

• 当前候选数等于nums[i]，票数+1
• 当前候选数不等于nums[i]
  • 票数大于0， 则票数-1
  • 票数等于0，则更新候选数为当前nums[i], 票数设为1

则最终的候选数即为最多元素。

例如：

ticket: 票数 
candidate: 候选数
数组： 2,2,1,1,1,2,2

        遍历值    票数   候选数
初始化:   2        1      2 
         2        2      2
         1        1      2
         1        0      2
         1        1      1
         2        0      1
         2        1      2
最终候选数为2，则2为多数元素