VariousAlgorithms

2020-05-06

Record some unfamiliar algorithms

1. 多数投票算法(Boyer-Moore Algorithm)详解

This algorithm serves to finding the major element in a pile of data, and the occurrence of the major element is no less than 50% of the whole.

Question Description:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. (Leetcode 169)

Brute force

HashMap

Double loop

Application

This algorithm logically partitions the elements to two sections. One is the section contains only major elements and the other one contains any other elements.

该算法时间复杂度为O(n)，空间复杂度为O(1)，只需要对原数组进行两趟扫描，并且简单易实现。第一趟扫描我们得到一个候选节点candidate，第二趟扫描我们判断candidate出现的次数是否大于⌊ n/2 ⌋。

第一趟扫描中，我们需要记录2个值：

candidate，初值可以为任何数
count，初值为0
之后，对于数组中每一个元素，首先判断count是否为0，若为0，则把candidate设置为当前元素。之后判断candidate是否与当前元素相等，若相等则count+=1，否则count-=1。

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

Extension

分布式Boyer-Moore
Boyer-Moore还有一个优点，那就是可以使用并行算法实现。相关算法可见Finding the Majority Element in Parallel
其基本思想为对原数组采用分治的方法，把数组划分成很多段(每段大小可以不相同)，在每段中计算出candidate-count二元组，然后得到最终结果。

举个例子，原数组为[1,1,0,1,1,0,1,0,0]
划分1：
[1,1,0,1,1] –> (candidate,count)=(1,3)
划分2：
[0,1,0,0] –> (candidate,count)=(0,2)
根据(1,3)和(0,2)可得，原数组的多数元素为1.

正因为这个特性，考虑若要从一个非常大的数组中寻找多数元素，数据量可能多大数百G，那么我们甚至可以用MapReduce的方式来解决这个问题。