Boyer-Moore 投票算法及其应用

本文主要是介绍Boyer-Moore 投票算法及其应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.什么是Boyer-Moore 投票算法,BM算法的应用在什么地方？

2.具体案例

3.参考

1.什么是Boyer-Moore 投票算法,BM算法的应用在什么地方？

BM算法包括两个阶段，第一个阶段是投票阶段，第二个阶段是计数阶段

投票阶段是从第一个数候选值开始，相同则c+=1,不同则c-=1,如果c为0，则替换候选值为新的候选值。

统计阶段是对候选值进行验证，判断候选值是否符合条件，因为不是所有的候选值都符合条件。

主要的应用场景：求解众数，寻找超过n/3的所有的数

2.具体案例

题目地址：https://leetcode-cn.com/problems/majority-element/

1.求解众数要求时间复杂度O(n),空间复杂度O(1)

代码如下

public static void main(String[] args) {
//        int[] arr = {1, 2, 3, 2, 2, 2, 5, 4, 2};int[] arr = {3, 3, 4};int num = majorityElement(arr);System.out.println("num:" + num);int num2 = majorityElement2(arr);System.out.println("num2:" + num2);}//Boyer-Moore 投票算法//应用求解众数//https://leetcode-cn.com/problems/majority-element/public static int majorityElement(int[] nums) {int candidate = nums[0];int count = 0;//投票阶段for (int i = 0; i < nums.length; i++) {if (candidate == nums[i]) {count++;continue;}if (count == 0) {candidate = nums[i];count = 1;continue;}count--;}//计数阶段int count2 = 0;for (int i = 0; i < nums.length; i++) {if (candidate == nums[i]) {count2++;if(count2>nums.length/2){return candidate;}}}return -1;}//使用hashmap计算众数public static int majorityElement2(int[] nums) {HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; i++) {if (map.get(nums[i]) == null) {map.put(nums[i], 1);} else {map.put(nums[i], map.get(nums[i]) + 1);}}int key = -1;int count = -1;for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if (entry.getValue() > count) {count = entry.getValue();key = entry.getKey();}}return key;}

题目地址：https://leetcode-cn.com/problems/majority-element-ii/

2.寻找超过n/3的数

代码如下

public static void main(String[] args) {int[] arr={1,1,1,3,3,2,2,2};List<Integer> list = majorityElement2(arr);System.out.println(list);}//ABBCBCAA//使用BM投票法//两个阶段 1.投票阶段 2.计数阶段// [A 1]  [A1  B1]  [A1  B2]  [A0  B1]  [A0  B2] [C1 B2] [C0 B1] [A1 B1]//https://leetcode-cn.com/problems/majority-element-ii/public static List<Integer> majorityElement2(int[] nums) {int num1 = nums[0];int count1 = 0;int num2 = nums[0];int count2 = 0;//投票阶段for (int i = 0; i < nums.length; i++) {if (num1 == nums[i]) {count1++;continue;}if (num2 == nums[i]) {count2++;continue;}if (count1 == 0) {num1 = nums[i];count1=1;continue;}if (count2 == 0) {num2 = nums[i];count2=1;continue;}count1--;count2--;}//计数阶段int count3 = 0;int count4 = 0;List<Integer> list=new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (nums[i] == num1 ) {count3++;continue;}if (nums[i] == num2 ) {count4++;continue;}}if(count3>nums.length/3 ){list.add(num1);}if(count4>nums.length/3 ){list.add(num2);}return list;}