摩尔投票众数法,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