169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

HashMap counting:

#![allow(unused)]
fn main() {
// time O(n), space O(n)
pub fn majority_element(nums: Vec<i32>) -> i32 {
    let mut cnt: HashMap<i32, i32> = HashMap::new();
    let mut res = 0;
    let mut max = 0;
    for num in nums {
        let v = cnt.entry(num).or_insert(0);
        *v += 1;
        if *v > max {
            res = num;
            max = *v;
        }
    }

    res
}
}

Sort and take the middle:

#![allow(unused)]
fn main() {
pub fn majority_element_sort(nums: Vec<i32>) -> i32 {
    let mut nums = nums;
    nums.sort();

    nums[nums.len() / 2]
}
}

Boyer-Moore voting:

#![allow(unused)]
fn main() {
// time O(n), space O(1)
pub fn majority_element_boyer_moore(nums: Vec<i32>) -> i32 {
    let mut res = 0;
    let mut cnt = 0;
    for num in nums {
        if cnt == 0 {
            res = num;
        }
        cnt += if num == res { 1 } else { -1 };
    }

    res
}
}

Randomization:

#![allow(unused)]
fn main() {
// time O(n) expected, space O(1)
pub fn majority_element_random(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    loop {
        let guess = nums[rand::rng().random_range(0..n)]; // let guess = nums[rand::random::<usize>() % n]; for leetcode
        let cnt = nums.iter().filter(|&&x| x == guess).count();
        if cnt > n / 2 {
            return guess;
        }
    }
}
}