摩尔投票算法

摩尔投票算法(Boyer-Moore majority vote algorithm)

​ 该算法是一种在线性时间O(n)和空间复杂度的情况下，在一个元素序列中查找包含最多的元素，是典型的流算法。

Leetcode 主要元素

如果数组中多一半的数都是同一个，则称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int majorityElement(vector<int>& nums) {
     int cnt = 1;
     int major = nums[0];
     int len = nums.size();
     for(int i = 1; i<len; i++)
     {
        if(cnt == 0)
        {
            cnt++;
            major = nums[i];
        }
        else if(major == nums[i])
            cnt++;
        else
            cnt--;
     }
    return major;
}

• ← Previous Post
• Next Post →