目录

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 map = new HashMap();
        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 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 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 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 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;
    }

3.参考

1.https://zhuanlan.zhihu.com/p/76518429---BM算法