摩尔投票算法( Boyer-Moore Voting Algorithm)

一、Majority Element题目介绍：给定一个长度为n的数组的时候，找出其中的主元素，即该元素在数组中出现的次数大于n/2的取整。题目中已经假定所给的数组一定含有元素，且主元素一定存在。一下是一些常用方法：

遍历每一个元素，并计数
排序法

二、摩尔投票算法：摩尔投票算法的时间和空间都很低，时间复杂度为O(n)，空间复杂度为O(1)，这也是选择遮盖算法的原因。

摩尔投票算法是一种在线性时间O(n)和线性空间复杂度下，在一个元素序列中，查找出现次数最多的元素；

算法实现

1.定义两个变量：m存储当前变量到的元素，count为计数器，初始情况下，count=0；

2.依次遍历数组中的每个元素，当遍历到元素x时，

如果count == 0，那么m=x，然后将count=1；

如果count != 0，将m与x进行比较，如果相等，count++；如果不等，count--；

3.处理完后，最后m存储的值就是这个序列中最多的元素；

int MajorityVote(vector<int> nums) {

    int res = 0, cnt = 0;

    for (auto &num : nums) {

        if (cnt == 0) {

            res = num;

            cnt++;

        }

        else if (num == res)cnt++;

        else cnt--;

    }

    return res;

}

三、摩尔投票算法的改进：

1，题目： LeetCode 229 [Majority Element II]

给定一个整型数组，找到所有主元素，它在数组中的出现次数严格大于数组元素个数的三分之一。

算法：每次删除三个不相同的数，最后留下的一定是出现次数超过1/3的数，这个思想可以推广到出现次数超过1/k次的元素有哪些。

因为出现次数大于n/3的元素最多只有两个，所以最开始可以维护两个数字(num1,num2)和两个计数器(counter1,counter2)；

遍历数组，当数组中元素和num1或者num2相同，对应的counter1或者counter2加1；

如果counter1或counter2为0，将遍历到的该元素赋给num1或者nums2；

否则counter1和counter2都减1。

C++代码

class Solution {

public:

    vector<int> majorityElement(vector<int>& nums) {

        vector<int> re;

        if (nums.size()==0) return re;

        int candidate1 = 0;

        int count1 = 0;

        int candidate2 = 0;

        int count2 = 0;

        for (int i=0; i<nums.size(); i++) {

            if (nums[i] == nums[candidate1]) count1++;

            else if (nums[i] == nums[candidate2]) count2++;

            else if (count1==0) {

                candidate1 = i;

                count1 = 1;

            }

            else if (count2==0) {

                candidate2 = i;

                count2 = 1;

            }

            else {

                count1--;

                count2--;

            }

        }

        count1 = 0;

        count2 = 0;

        for (int i=0; i<nums.size(); i++) {

            if (nums[i] == nums[candidate1]) count1++;

            else if (nums[i] == nums[candidate2]) count2++;

        }

        if (count1 > nums.size()/3) re.push_back(nums[candidate1]);

        if (count2 > nums.size()/3) re.push_back(nums[candidate2]);

        return re;

    }

};

巴特西

摩尔投票算法( Boyer-Moore Voting Algorithm)

C++代码

最新文章

热门文章