多数元素
也叫数组中出现次数超过一半的数字
给定一个大小为 *n *的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
方法一：排序+取中间元素
public int majorityElement(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
return nums[n / 2];
}
方法二：HashMap
统计每个数字出现次数，最后再做比较
方法三：摩尔投票
public int majorityElement(int[] nums) {
int candidate = 0;
int count = 0;
for (int num : nums) {
count += candidate == num ? 1 : -1;
if (count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
摩尔投票法，解决的问题是如何在任意多的候选人中，选出票数超过一半的那个人。注意，是超出一半票数的那个人。
假设投票是这样的，[A, C, A, A, B]，ABC 是指三个候选人。
第一张票与第二张票进行对坑，如果票不同则互相抵消掉；
接着第三票与第四票进行对坑，如果票相同，则增加这个候选人的可抵消票数；
这个候选人拿着可抵消票数与第五张票对坑，如果票不同，则互相抵消掉，即候选人的可抵消票数 -1。
但这不意味着这个候选人的票数一定能超过一半，例如 [A, B, C] 的抵消阶段，最后得到的结果是 [C,1]，C 候选人的票数也未能超过一半的票数。
在这里发现了一个优化，如果最后得到的可抵消票数是 0 的话，那他已经无缘票数能超过一半的那个人了。因为本来可能有希望的，但是被后面的一张不同的票抵消掉了。所以，在这里可以直接返回结果，无需后面的计算了。
如果最后得到的抵消票数不为 0 的话，那说明他可能希望的，这是我们需要一个阶段来验证这个候选人的票数是否超过一半—— 计数阶段。
所以摩尔投票法分为两个阶段：抵消阶段和计数阶段。
抵消阶段：两个不同投票进行对坑，并且同时抵消掉各一张票，如果两个投票相同，则累加可抵消的次数；
计数阶段：在抵消阶段最后得到的抵消计数只要不为 0，那这个候选人是有可能超过一半的票数的，为了验证，则需要遍历一次，统计票数，才可确定。
摩尔投票法经历两个阶段最多消耗O(2n) 的时间，也属于 O(n)的线性时间复杂度，另外空间复杂度也达到常量级。
为了和下一题统一写成：
public int majorityElement(int[] nums) {
int candidate = nums[0];
int vote = 0;
for (int num : nums) {
if (vote > 0 && num == candidate) {
vote++;
} else if (vote == 0) {
candidate = num;
vote = 1;
} else {
vote--;
}
}
return candidate;
}
求众数 II
给定一个大小为 *n *的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
摩尔投票
题目可以看作是：在任意多的候选人中，选出票数超过⌊ 1/3 ⌋的候选人。
我们可以这样理解，假设投票是这样的 [A, B, C, A, A, B, C]，ABC 是指三个候选人。
第 1 张票，第 2 张票和第3张票进行对坑，如果票都不同，则互相抵消掉；
第 4 张票，第 5 张票和第 6 张票进行对坑，如果有部分相同，则累计增加他们的可抵消票数，如 [A, 2] 和 [B, 1]；
接着将 [A, 2] 和 [B, 1] 与第 7 张票进行对坑，如果票都没匹配上，则互相抵消掉，变成 [A, 1] 和 `[B, 0] 。
如果至多选一个代表，那他的票数至少要超过一半（⌊ 1/2 ⌋）的票数；
如果至多选两个代表，那他们的票数至少要超过 ⌊ 1/3 ⌋ 的票数；
如果至多选m个代表，那他们的票数至少要超过 ⌊ 1/(m+1) ⌋ 的票数。
所以以后碰到这样的问题，而且要求达到线性的时间复杂度以及常量级的空间复杂度，直接套上摩尔投票法。
public List<Integer> majorityElement(int[] nums) {
// 投票阶段
int candidate1 = nums[0], candidate2 = nums[0];
int vote1 = 0, vote2 = 0;
for (int i = 0; i < nums.length; i++) {
if (vote1 > 0 && nums[i] == candidate1) {
vote1++;
} else if (vote2 > 0 && nums[i] == candidate2) {
vote2++;
} else if (vote1 == 0) {
candidate1 = nums[i];
vote1 = 1;
} else if (vote2 == 0) {
candidate2 = nums[i];
vote2 = 1;
} else {
vote1--;
vote2--;
}
}
// 计数阶段
int cnt1 = 0, cnt2 = 0;
for (int num : nums) {
if (num == candidate1) {
cnt1++;
} else if (num == candidate2) {
cnt2++;
}
}
// 判断是否满足条件
List<Integer> res = new ArrayList<>();
if (vote1 > 0 && cnt1 > nums.length / 3) {
res.add(candidate1);
}
if (vote2 > 0 && cnt2 > nums.length / 3) {
res.add(candidate2);
}
return res;
}
