# majority voting algorithm

### Majority Voting Algorithm

• 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.