README.md

229. Majority Element II

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 5 * 104
• -109 <= nums[i] <= 109

Follow up: Could you solve the problem in linear time and in O(1) space?

Solutions (Rust)

1. Solution

impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut majorities = [(i32::MAX, 0); 2];

        for num in &nums {
            if let Some(i) = majorities.iter().position(|(x, _)| x == num) {
                majorities[i].1 += 1;
            } else if let Some(i) = majorities.iter().position(|&(_, c)| c == 0) {
                majorities[i] = (*num, 1);
            } else {
                for i in 0..2 {
                    majorities[i].1 -= 1;
                }
            }
        }

        for i in 0..2 {
            majorities[i].1 = 0;
        }

        for num in &nums {
            if let Some(i) = majorities.iter().position(|(x, _)| x == num) {
                majorities[i].1 += 1;
            }
        }

        majorities
            .into_iter()
            .filter(|&(x, c)| *c > n / 3)
            .map(|(x, _)| *x)
            .collect()
    }
}