Problem
In a provided vector vec we need to find the majority element, if it is present. The majority element is the element that appears in the vector more than n / 2 times, where n is a size of the vector vec.
Example 1:
Input: vec = [4, 8, 7, 4, 4, 5, 4, 3, 1, 4, 4]
Output: 4
Explanation: The majority element is 4 because it appears in the vector 6 times (more than n / 2 = 11 / 2 = 5).
Example 2:
Input: vec = [4, 8, 7, 4, 4, 5, 4, 3, 1, 4]
Output: None
Explanation: There is no the majority element in the vector. Even though 4 is the most common element, it is not the majority element, because it appears only 5 times (not more than n / 2 = 10 / 2 = 5 times).
Example 3:
Input: vec = [1]
Output: 1
Example 4:
Input: vec = [1, 2]
Output: None
Solution
fn find_majority_element(vec: &Vec<i32>) -> Option<i32> {
let mut m = 0;
let mut i = 0;
//first pass:
vec.iter().for_each(|&x| {
if i == 0 {
m = x;
i = 1;
} else if m == x {
i = i + 1;
} else {
i = i - 1;
}
});
//second pass:
let count = vec
.iter()
.fold(0, |count, &x| if x == m { count + 1 } else { count });
//return Some(m) if actual majority, None otherwise:
(count > vec.len() / 2).then(|| m)
}
Explanation
The solution for this problem uses Boyer–Moore majority vote algorithm:
Initialize an element m and a counter i with i = 0
For each element x of the input sequence:
If i = 0, then assign m = x and i = 1
else if m = x, then assign i = i + 1
else assign i = i − 1
Return m
Also we need the second pass over the vector vec because, even when there is no the majority element, the algorithm would yield one of the elements as the result (m). On the second pass, we calculate a number of times (count) we encounter m element to check if that is the actual majority (it appears more than vec.len() / 2 times). If that is the case - we found the majority element. If not - we return None.
Complexity
The time complexity of this solution is O(n) (n is a size of the input vector), but we need to iterate over the input vector twice. The auxiliary space complexity is constant (O(1)).