摩尔投票算法
摩尔投票算法
摩尔投票算法是一种用于在数组中查找出现次数超过一半的元素的有效算法。算法的核心思想是利用候选元素和[计数器](https://so.csdn.net/so/search?q=%E8%AE%A1%E6%95%B0%E5%99%A8&spm=1001.2101.3001.7020)进行投票,通过消除不同元素之间的抵消来找到出现次数超过一半的元素。
算法原理
如果数组中存在一个出现次数超过一半的元素,那么这个元素的剩余部分一定会抵消其他元素的出现次数,最终剩下的就是该元素。
算法步骤
初始化候选元素 candidate 为数组的第一个元素,计数器 count 为 1。
从数组的第二个元素开始遍历。
如果当前元素与候选元素相同,则将计数器 count 加 1。
如果当前元素与候选元素不同,则将计数器 count 减 1。
如果计数器 count 减为零,则更新候选元素为当前元素,并将计数器 count 重置为 1。
完成遍历后,候选元素就是出现次数超过一半的元素。
实例
例子:
假设数组为 [2, 2, 1, 1, 1, 2, 2]。
初始时, ...
记录
记录
谢益辉的个人博客
阮一峰的网络日志
Lcomplete 野生架构师
胡涂说
4Ark
程序员的喵
Limboy
食灯鬼
风清的精神角落
Innei
Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
Quick StartCreate a new post1$ hexo new "My New Post"
More info: Writing
Run server1$ hexo server
More info: Server
Generate static files1$ hexo generate
More info: Generating
Deploy to remote sites1$ hexo deploy
More info: Deployment