前言

想要精通算法和SQL的成长之路 - 系列导航

一. 多数元素

原题链接

1.1 摩尔投票法

简单来说，假设数组 num 的众数是 x，数组长度为n。
有两个推论：

• 我们有一个票数和为sum，若记众数的票数为 +1 ，非众数的票数为 −1 ，则一定有所有数字的票数和 sum >0 。
• 如果数组的前 m 个数字的票数和为0，那么剩余的(n-m) 个数字的票数和一定 > 0，并且后面(n-m)个数字中的众数依旧是x。

那么针对本题目，求得的是多数元素，其出现次数超过数组元素个数的一半。思路如下：

• 我们设置当前众数为：res。初始化为数组第一元素。
• 设置当前票数和为：vote。初始化为0
• 遍历数组：如果票数和为0，更新众数为当前元素。
• 每次遍历，都对票数做统计，是众数，则+1，否则-1。

结果如下：

public int majorityElement(int[] nums) {int res = nums[0], vote = 0;for (int num : nums) {if (vote == 0) {res = num;}vote += (res == num) ? 1 : -1;}return res;
}

二. 多数元素II

原题链接

在原题的基础上，不再是求出现次数超过2分之一的多数元素了。而是三分之一。即本题的返回个数最多有两个。

2.1 分析

我们这里这里假设：有两个（并且最多只有两个）符合题目条件的元素：x 和 y。他们的票数分别是v1 和 v2。

1. 利用摩尔投票法，确定两个候选数。因为我们这里假设的是2个都满足条件，但是实际情况可能只有一个或者没有。这里只是求得：出现次数最多的前两个数是哪几个（实际他们的出现次数却不知道）
2. 最后再对这两个候选人做计数统计，统计他们分别出现的次数是多少，是否满足题目要求。

阶段一：摩尔投票阶段，决定出现次数最多的前两个数：

// 初始化两个候选数和对应票数
int x = nums[0], y = nums[0];
int v1 = 0, v2 = 0;
// 摩尔投票，求得出现次数最多的两个数
for (int num : nums) {// 如果当前数和x一样if (x == num) {v1++;continue;}// 如果当前数和x一样if (y == num) {v2++;continue;}// 第一个候选票数为0了，那么当前数认定为第一个候选数if (v1 == 0) {x = num;v1++;continue;}// 第二个候选 同理if (v2 == 0) {y = num;v2++;continue;}// 否则，都不满足两个候选，两个候选的票数同时-1v1--;v2--;
}

这时候，我们拿到票数最多的两个元素，x和y。他们可能是同一个元素，也可能不是同一个元素。

接下来进入阶段二，统计票数阶段：

// 阶段二：统计票数阶段
v1 = 0;
v2 = 0;
for (int num : nums) {if (num == x) {v1++;} else if (num == y) {v2++;}
}

注意：不能这么写：（两个数如果是同一个，那就重复了）

for (int num : nums) {if (num == x) {v1++;}if (num == y) {v2++;}
}

最后，判断他们的出现次数是否满足条件，满足则加入结果集，所有代码如下：

public List<Integer> majorityElement(int[] nums) {ArrayList<Integer> res = new ArrayList<>();if (nums == null || nums.length == 0) {return res;}// 初始化两个候选数和对应票数int x = nums[0], y = nums[0];int v1 = 0, v2 = 0;// 摩尔投票，求得出现次数最多的两个数for (int num : nums) {// 如果当前数和x一样if (x == num) {v1++;continue;}// 如果当前数和x一样if (y == num) {v2++;continue;}// 第一个候选票数为0了，那么当前数认定为第一个候选数if (v1 == 0) {x = num;v1++;continue;}// 第二个候选 同理if (v2 == 0) {y = num;v2++;continue;}// 否则，都不满足两个候选，两个候选的票数同时-1v1--;v2--;}// 阶段二：统计票数阶段v1 = 0;v2 = 0;for (int num : nums) {if (num == x) {v1++;} else if (num == y) {v2++;}}// 最后看看是否超过了三分之一if (v1 > nums.length / 3) {res.add(x);}if (v2 > nums.length / 3) {res.add(y);}return res;
}