Boyer-Moore 算法 Leetcode169
Boyer-Moore 算法 Leetcode169
一、题目
169. 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
二、解法
Java：
class Solution {
public int majorityElement(int[] nums) {
• int thatnum=nums[0];
• int count=0;
• for(int i=0;i<nums.length;i++)
• {
• if(count==0)
• {
• thatnum=nums[i];
• count++;
• }
• else if(nums[i]==thatnum)
• {
• count++;
• }else{
• count--;
• }
• }
• return thatnum;
}
}
三、思路
题目要求找到出现次数大于一半的数，我从这个算法的角度进行分析：
如果我们最终要得到得数为thatnum，其余的为othernum
它们在数组中和其他数的关系都有两种，一种是相等，一种是不相等
thatnum的个数超过数组总数的一半，因而，与thatnum相等的数个数要大于与thatnum不相等的数的个数
而对于othernum，它的个数显然小于总数的一半，因此有超过一半的数是和它不相等的，所以与它相等的数的个数要小于与它不相等的个数
最后，用count作为记录，当有数与当前thatnum相等的时候，count++,正向
当有数与当前thatnum不等的时候，count–反向
当count==0时，意味着当前thatnum的相等和不相等数抵消，则重新取一个新的thatnum
根据以上的原理，thatnum总是相等的数个数多于不相等的，因此最终不会被抵消,而othernum最终会被抵消
最后可以参考这个算法动手一试便可加深理解。
版权声明：本文为zhang-qi123原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。