A Fast Majority Vote Algorithm
date
Jul 17, 2022
slug
mjrty
status
Published
tags
DSAA
summary
中文名为 “摩尔投票算法”
type
Post
解决的问题：假设数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。使用该算法可以在时间复杂度为 O(n)，空间复杂度为 O(1) 的条件下找出这个数字。
想象一下，现在有许多帮派打群架，帮派内部没有内奸，每个帮派的人都可以与不同帮派的人一换一。结束时，只会剩下一个帮派的的人，这个帮派就是帮派人数最多的人。而这，也是算法的思路。
该算法相关的资料和示例网站：