Boyer–Moore Majority Vote Algorithm摩尔投票法，众数算法，Java

￡神魔★判官ぃ 2023-09-28 08:39 120阅读 0赞

摩尔投票众数法，Boyer–Moore Majority Vote Algorithm，也被称作多数投票法，求解众数的算法（Majority Vote Algorithm），算法找出一个数组中超过一半的那个元素。

该算法特别适合流式数据计算环境（实时的流式大数据），某一个值是否超过总量的一半。该算法十分巧妙，时间复杂度为线性时间O(n)，且不需要引入额外的空间复杂（例如最常规的hashmap之类，逐一记录每个元素出现的个数）。

public static void main(String[] args) {
            int count = 10;
            int[] data = dummy(count);
            int major = majority(data);
            System.out.println("结果:" + major);
        }
    
        // 制作测试数据。假设数据总数为count。
        // 前一半-1（count/2 - 1）个数字是随机数，后一半+1个数字(count/2 +1)重复一个数字即众数。然后随机打乱这些数据。
        // 如果刚好众数占一半，那么该算法并不总能工作良好，所以必须把众数多于一半。
        public static int[] dummy(int count) {
            int[] data = new int[count];
    
            final int major = (int) (Math.random() * 100);
            System.out.println("众数:" + major);
    
            for (int i = 0; i < count; i++) {
                if (i < (count / 2 - 1)) {
                    data[i] = (int) (Math.random() * 100);
                } else {
                    data[i] = major;
                }
            }
    
            //Java8以上
            //int[]数组转为List<Integer>
            List<Integer> list = Arrays.stream(data).boxed().collect(Collectors.toList());
            System.out.print("原数据:");
            System.out.print(list);
    
            Collections.shuffle(list);
            System.out.print("\n打乱后:");
            System.out.println(list);
    
            //Java8以上
            //再将List<Integer>转为普通的int[]数组
            int[] intArr = list.stream().mapToInt(Integer::intValue).toArray();
            return intArr;
        }
    
        // 众数的核心执行算法。
        // 传入一个数组，最终返回该数组中的众数。
        public static int majority(int[] nums) {
            //初始化，假设数组中第一个数即为众数
            int major = -1;
            int count = 0;
    
            for (int i = 0; i < nums.length; i++) {
                if (count == 0) {
                    major = nums[i];
                    count = 1;
                } else {
                    if (major == nums[i]) {
                        count++;
                    } else {
                        count--;
                    }
                }
            }
    
    
            //统计最终获得的众数major，是否真的超过一半？
            int cnt = 0;
            for (int n : nums) {
                if (n == major) {
                    cnt++;
                }
            }
    
            if (cnt > nums.length / 2) {
                //正常
            } else {
                major = -1;//原数据异常，没有数超过总量的一半。
            }
    
    
            return major;
        }

测试输出：

众数:99
    原数据:[31, 75, 40, 49, 99, 99, 99, 99, 99, 99]
    打乱后:[40, 99, 99, 99, 31, 75, 99, 99, 99, 49]
    结果:99