AcWing52. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

假设数组非空，并且一定存在满足条件的数字。

思考题：

  • 假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？

数据范围

数组长度 [1,1000]。

样例

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

输出：1

算法思想

  1. 计数器（最受欢迎的选举人票数）：cnt
  2. 主元（最受欢迎的选举人）：val
  3. 核心思想：新的选举人可以消耗最受欢迎的选举人的票

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 0, val;
        
        for(int i = 0; i < nums.size(); i++){
            if(!cnt) val = nums[i], cnt++;
            else if(nums[i] == val) cnt++;
            else cnt--;
        }
        
        return val;
    }
};