用摩尔投票法寻找数组中数量超过一半的成员

题目链接-来源：力扣（LeetCode）

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

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

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

思路：

题目给出数组中存在一个出现次数超过一半的成员，那么我们可以用「摩尔投票法」找出他。
「摩尔投票法」核心思路就是，遍历数组中的成员，出现相同的成员会累计，而不同的成员会抵消。那么只要确保有数量超过一半的某种成员，便可「活到最后」，拥有不为0的计数，这便是我们要找的那个成员。
具体实现当中，我们需要一个变量 prev 存储当前数量占优的那个元素，初始为 nums[0]，还需要用 votes 记录当前占优元素的「票数」，或者说「存活个数」。当 votes 变化到0时，我们认为当前的「优势元素」prev 可能发生了变化，于是取当前访问到的数组成员为新的 「优势元素」。遇到与「优势元素」相同的元素则票数增加，反之减少。这样经过完整遍历后，数组中超过一半数量的那个成员一定能活到最后。
时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length;
        int votes = 0;
        int prev = 0;
        for (int i = 0; i < len; i++) {
            if (votes == 0) {
                prev = nums[i];
            }
            if (nums[i] == prev) {
                votes++;
            } else {
                votes--;
            }
            
        }
        return prev;
    }
}