精巧的 Boyer-Moore 投票算法

作者：皓月

2022 年 4 月 28 日
本文字数：2286 字
阅读完需：约 8 分钟

在用于查找子字符串的算法当中，BM（Boyer-Moore）算法被认为最高效的字符串搜索算法，它由 Bob Boyer 和 J Strother Moore 设计于 1977 年。一般情况下，比 KMP 算法快 3-5 倍。该算法常用于文本编辑器中的搜索匹配功能，比如大家所熟知的 GNU grep 命令使用的就是该算法，这也是 GNU grep 比 BSD grep 快的一个重要原因。
https://baike.baidu.com/item/Boyer-%20Moore%E7%AE%97%E6%B3%95/16548374?fr=aladdin

了解该算法前，我们首先思考一道 LeetCode 上面原题，该题有多种解法，其中最常见的做法是分治递归的解题思路，如下：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 
示例 1：
输入：nums = [3,2,3]输出：3示例 2：
输入：nums = [2,2,1,1,1,2,2]输出：2
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/majority-element著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {    private int countInRange(int[] nums, int num, int lo, int hi) {        int count = 0;        for (int i = lo; i <= hi; i++) {            if (nums[i] == num) {                count++;            }        }        return count;    }
    private int majorityElementRec(int[] nums, int lo, int hi) {        // base case; the only element in an array of size 1 is the majority        // element.        if (lo == hi) {            return nums[lo];        }
        // recurse on left and right halves of this slice.        int mid = (hi - lo) / 2 + lo;        int left = majorityElementRec(nums, lo, mid);        int right = majorityElementRec(nums, mid + 1, hi);
        // if the two halves agree on the majority element, return it.        if (left == right) {            return left;        }
        // otherwise, count each element and return the "winner".        int leftCount = countInRange(nums, left, lo, hi);        int rightCount = countInRange(nums, right, lo, hi);
        return leftCount > rightCount ? left : right;    }
    public int majorityElement(int[] nums) {        return majorityElementRec(nums, 0, nums.length - 1);    }}
作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制代码

上面代码不难理解，基本思路是将数组从中间切分成左右子数组，然后分别求解，在子数组里面寻找出现次数最多元素，然后再逐层返回到最开始的一层，就得到最终的结果，算法简单易懂，但时间复杂度为 n log n, 首先，进行数组长度的次数遍历，同时在遇到左右出现次数最多元素不一样时，也有机会会再次进行元素个数统计，扫秒的数组长度逐层减少，每次减少 1/2，因此为 log n, 总时间复杂度为 n log n.

空间复杂度，起始没有额外的空间产生，但迭代产生了额外的栈空间，也为 log n.

怎么样，大部分同学能把该题目做到这里已经很不错了，时间和空间复杂都不算高。

但....

总有更加高明和精巧的思路和方法，这也是计算机科学的魅力所在, 也是算法的魅力之处，它能让你恍然大悟，让你感叹人类智慧和计算机科学的博大之处，它远比你想象强大，但这种强大也需要依附人的思维能力，只要你运用合理，它就能产生更大的价值。正如我们大部分人都能运用编程让计算机完成指定的任务，但有的程序性能和资源消耗的表现都差强人意，而有的程序却能用更少的计算机资源完成更多的任务，这就是建立在人的思维能力和对计算机原理的深入理解之上，并且需要通过大量测试和时间完成。举个例，在 Nginx 出现之前其实软件代理服务器就很流行了，而且种类繁多, 如 Apache httpd, 但出自俄罗斯程序员之手的 Nginx 无论是性能和受欢迎程度都远超过后者，其设计思路和架构不可谓不优秀(epoll 模型)。http://nginx.org/en/docs/

说回正题，Boyer-Moore 投票算法，可以说是将人类智慧在计算机上发挥到极致的案例，现在我们重新解上面的问题。

    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;        }    }作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制代码

怎么样？15 行代码，时间复杂度 O(n), 空间复杂度 O(n), 何为投票，我们进行选举活动时的投票，可以有反对票也可以有赞成票，在该算法里面就充分运用这种机制，要想找出多数元素，那就进行投票，遍历数组，当前元素与候选元素一致就投赞成票，投票器+1，如果不一样就-1，投票器归 0 时就重新指定候选元素，将坚持到最后的候选元素返回。更加简单、更加易懂（完全是人的思维模式），但得到的却是常数级的时间和空间复杂度。

发布于: 刚刚阅读数: 6

皓月

关注

不积跬步无以至千里。 2021.06.28 加入

个人代码库：https://gitee.com/hon-gitee, 欢迎来踩~~。

发布

暂无评论

创作场景

精巧的 Boyer-Moore 投票算法

皓月

评论