网站建设定制公司推荐,网页设计公司的市场定位,门户网站 特点,成都建设门户网站目录 1.概述2.算法思想3.代码实现3.1.t ⌊n / 2⌋3.2.t ⌊n / 3⌋3.3.t ⌊n / (m 1)⌋ 4.应用 参考#xff1a;LeetCode_多数元素 II 题解 1.概述
#xff08;1#xff09;摩尔投票法 (Boyer–Moore Majority Vote Algorithm) 是一种用来寻找一组元素中多数元素的常量级… 目录 1.概述2.算法思想3.代码实现3.1.t ⌊n / 2⌋3.2.t ⌊n / 3⌋3.3.t ⌊n / (m 1)⌋ 4.应用 参考LeetCode_多数元素 II 题解 1.概述
1摩尔投票法 (Boyer–Moore Majority Vote Algorithm) 是一种用来寻找一组元素中多数元素的常量级空间复杂度算法。一般来说摩尔投票法常用于求众数求众数这个问题本身比较简单但是想要使用常量级空间复杂度来实现却不是那么简单。而摩尔投票法正是这样一种算法。
2众数 (Mode) 是指在统计分布上具有明显集中趋势点的数值代表数据的一般水平。 也是一组数据中出现次数最多的数值有时众数在一组数中有好几个。用 M 表示。上面提到的多数元素与众数的含义差不多只不过在摩尔投票法算法中多数元素是指在数组长度为 n中出现次数大于某个阈值 (t) 的元素并且存在如下结论
如果 t ⌊n / 2⌋那么多数元素最多只有 1 个如果 t ⌊n / 3⌋那么多数元素最多只有 2 个如果 t ⌊n / (m 1)⌋那么多数元素最多只有 m 个
2.算法思想
1摩尔投票法的核心思想为对拼消耗。首先我们考虑最基本的摩尔投票问题比如找出一组数字序列中出现次数大于 ⌊n / 2⌋ 的数字并且假设这个数字一定存在。我们可以直接利用反证法证明这样的数字只可能有一个
假设我们当前数组中存在次数大于总数一半的元素为 x数组的总长度为 n则我们可以把数组分为两部分 一部分为相同的 k 个元素 x另一部分为 n − k 2 \frac{n - k}{2} 2n−k 对个不同的元素配对 此时我们假设还存在另外一个次数大于总数一半的元素 y则此时 y 因该满足 y n 2 \frac{n}{2} 2n 但是按照我们之前的推理 y 应当满足 y ≤ n − k 2 \frac{n - k}{2} 2n−k 二者自相矛盾。
因此对于 t ⌊n / 2⌋摩尔投票算法的核心思想是基于这个事实每次从序列里选择两个不相同的数字删除掉或称为抵消最后剩下一个数字或几个相同的数字就是出现次数大于总数一半的那个元素。
2对于 t ⌊n / 3⌋我们可以利用反证法推断出满足这样条件的元素最多只有两个同理我们可以利用摩尔投票法的核心思想每次选择三个互不相同的元素进行删除或称为「抵消」推导思路如下
假设数组中一定只存在一个次数大于 ⌊ n 3 \frac{n}{3} 3n⌋ 的元素 x则此时我们可以把数组分成两部分一部分相同的 k 个元素 x另一部分为 n − k 3 \frac{n - k}{3} 3n−k 组三个不同的元素我们知道三个不同的元素会被抵消因此最终只会剩下一个元素为 x。如果只存在 2 个次数大于 ⌊ n 3 \frac{n}{3} 3n⌋ 的元素时假设这两个不同的元素分别为 x 和 y则此时我们一定可以把数组分成三部分第一部分相同的 m 个元素 x第二部分相同的 k 个元素 y第三部分为 n − m − k 3 \frac{n - m - k}{3} 3n−m−k 组三个互不同的元素我们知道三个互不同的元素会被抵消因此最终只会剩下两个元素为 x 和 y。
具体思路如下
我们每次检测当前元素是否为第一个选中的元素或者第二个选中的元素每次我们发现当前元素与已经选中的两个元素都不相同则进行抵消一次如果存在最终选票大于 0 的元素我们还需要再次统计已选中元素的次数,检查元素的次数是否大于 ⌊ n 3 \frac{n}{3} 3n⌋。
3对于 t ⌊n / (m 1)⌋我们可以利用同样的方法推断出满足这样条件的元素最多只有 m 个。但是需要注意的是此时算法时间复杂度为 O(n * m)空间复杂度为 O(m)。
3.代码实现
3.1.t ⌊n / 2⌋
class Solution {public int majorityElement(int[] nums) {//设 candidate 为出现次数大于 ⌊n / 2⌋ 的元素int candidate 0;int cnt 0;//遍历数组 numsfor (int num : nums) {if (cnt 0) {//重新确定选举人candidate num;}if (num candidate) {//candidate 的票数加一cnt;} else {//对拼消耗即相当于 candidate 的票数减一cnt--;}}return candidate;}
}① 上述算法的时间复杂度为 O(n)空间复杂度为 O(1)。 ② 有关 t ⌊n / 2⌋ 的摩尔投票算法的具体细节可以参考本题官方题解。 3.2.t ⌊n / 3⌋
class Solution {public ListInteger majorityElement(int[] nums) {//满足题目条件的元素最多只有两个我们设为 ele1 和 ele2int ele1 0;int ele2 0;//设 vote1 和 vote2 分别为 ele1 和 ele2 的赞成票数int vote1 0;int vote2 0;for (int num : nums) {if (vote1 0 num ele1) {//num 为第一个元素则票数加 1vote1;} else if (vote2 0 num ele2) {//num 为第二个元素则票数加 1vote2;} else if (vote1 0) {//选择第一个元素ele1 num;vote1;} else if (vote2 0) {//选择第二个元素ele2 num;vote2;} else {//三个元素 ele1、ele3、num 互不相同则其票数减 1即对拼消耗vote1--;vote2--;}}//cnt1 和 cnt2 分别记录元素 ele1 和 ele2 出现的次数int cnt1 0;int cnt2 0;for (int num : nums) {if (vote1 0 num ele1) {cnt1;}if (vote2 0 num ele2) {cnt2;}}//检查元素出现的次数是否满足要求ListInteger res new ArrayList();if (vote1 0 cnt1 nums.length / 3) {res.add(ele1);} if (vote2 0 cnt2 nums.length / 3) {res.add(ele2);}return res;}
}上述算法的时间复杂度为 O(n)空间复杂度为 O(1)。 3.3.t ⌊n / (m 1)⌋
class Solution {public static ListInteger majorityElements(int[] nums, int m) {//存储多数元素的集合ListInteger res new ArrayList();//候选元素数组int[] candidates new int[m];//对应候选元素的计数器数组int[] counts new int[m];for (int num : nums) {//如果 num 存在于候选元素数组中则将对应计数器加 1for (int i 0; i m; i) {if (candidates[i] num) {counts[i];break;}//如果 num 不在候选元素数组中且有空位置计数器为 0则将 num 加入候选元素数组if (candidates[i] 0 counts[i] 0) {candidates[i] num;counts[i];break;}}//如果候选元素数组已满则将所有计数器减 1if (counts[m - 1] ! 0) {for (int i 0; i m; i) {counts[i]--;}}}//验证候选元素的计数器是否大于阈值for (int i 0; i m; i) {int count 0;for (int num : nums) {if (num candidates[i]) {count;}}if (count nums.length / (m 1)) {res.add(candidates[i]);}}return res;}
}4.应用
大家可以去 LeetCode 上找相关的 Boyer-Moore 投票算法的题目来练习或者也可以直接查看 LeetCode 算法刷题目录 (Java) 这篇文章中的 Boyer-Moore 投票算法章节。如果大家发现文章中的错误之处可在评论区中指出。
