首页 > itarticle > majority voting algorithm

majority voting algorithm

admin 11月 13, 2020 0

Majority Voting Algorithm

https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

  • Simple solution:
    • sort the list.
    • If there is a majority value, then it should be at the middle(or in the lc229 2/3) position.
    • time complexity: sort -> O(nlogn)
  • Boyer-Moore algorithm
    • time complexity: O(N), space complexity: O(1)
    • Two passes
      • First pass: Find the candidate
        • variable : candidate, count
        • traverse the list, if the current number is equal to candidate, then count++.
        • if the count is equal to 0 and the current number is not equal to the candidate, set the candidate as the current number and count++.
        • if the count is larger than 0 and the current number is not equal to the candidate, then count–.
      • Second pass: double check the candidate
        • traverse the list, count the number of members which is equal to candidate
        • if count > 1/2 list (or other) then return the candidate, else return false

LC 229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]
Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

1/3 list means that there may have 1 or 2 majority elements. So we need to set 2 candidate variables and 2 count variables.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
class  {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int candidate1 = 0, candidate2 = 1;
        int count1 = 0, count2 = 0;
        for(int n : nums){
            if(candidate1 == n)
                count1++;
            else if(candidate2 == n)
                count2++;
            else if(count1 == 0){
                candidate1 = n;
                count1 = 1;
            } else if(count2 == 0){
                candidate2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        vector<int> res;
        count1 = 0;
        count2 = 0;
        for(int n : nums){
            if(n == candidate1)
                count1++;
            if(n == candidate2)
                count2++;
        }
        if(count1 > nums.size() / 3)
            res.push_back(candidate1);
        if(count2 > nums.size() / 3)
            res.push_back(candidate2);
        return res;
    }
};
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能