Boyer-Moore 算法

2020 年 05 月 03 日 阅读数: 11

今天在做Leetcode上的这道找到数组中的majority element(https://leetcode.com/problems/majority-element/)题目时候,发现了一个有意思的算法,Boyer-Moore算法,可以在不借助哈希表和排序的情况下,以O(N)的时间复杂度来解决这个问题。

排序

如果我们首先将数组进行排序,然后直接返回中间的数,那么这个数字肯定是majority element。

import "sort"
func majorityElement(nums []int) int {
sort.Ints(nums)
return nums[len(nums)/2]
}

简洁, 时间复杂度为O(NlogN), 空间复杂度为常数项。

哈希

用哈希表记录下每个数字出现的次数,然后当某个数字出现的次数超过1/2的时候,就可以将其返回。

func majorityElement(nums []int) int {
dict := make(map[int]int)
for _, n := range nums {
dict[n]++
if dict[n] > len(nums) /2 {
return n
}
}
return -1
}

时间复杂度为O(N),但是空间复杂度为O(N),并且涉及到哈希表的读取写入和扩容,实际时间并不快。

Boyer-Moore算法

该算法可以用O(1)的空间复杂度和O(N)的时间复杂度来解决此类问题,最早在这篇论文(http://www.cs.rug.nl/~wim/pub/whh348.pdf)中被提出。我们先看看代码

func majorityElement(nums []int) int {
count, res := 0, nums[0]
for _, n := range nums[1:] {
if count == 0 {
res = n
}
if n == res {
count++
} else {
count--
}
}
return res
}

我们可以假设majority element为s, 那么数组可以视为[a...s...c...s...b..d...s...s], 也就是各个s元素之间穿插着其他的元素,由于s的数量超过所有的元素加起来的数量,那么至少有两个s元素连在一起,那么上述的count最终肯定为正数,并且res就为我们要找的元素。

假设输入为

[5, 5, 0, 0, 0, 5, 0, 0, 5]

  1. res为5, count++ 一直到2

  2. 遇到0,count-- 到1

  3. 遇到0, count-- 到0

  4. res为0, count++ 为1

  5. 遇到5, count-- 到0

  6. res为5, count++ 为1

  7. 遇到0, count-- 到0

  8. res为0, count++ 为1

  9. 遇到0, count++ 到2

  10. 遇到5, count-- 为1

  11. 返回5作为majority element

总结

Boyer-Moore算法虽然并不直观,但是有良好的时间复杂度和空间复杂度,并且实现的代码非常简洁干净,多思考算法中所蕴含的逻辑有助于掌握该算法。

Reference

  1. https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

用户头像

Kenn

关注

忘记密码 记住我 2018.03.09 加入

Démon de Laplace

评论

发布
暂无评论
Boyer-Moore 算法