README_CN.md

229. 多数元素 II

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1:

输入: nums = [3,2,3]
输出: [3]

示例 2:

输入: nums = [1]
输出: [1]

示例 3:

输入: nums = [1,2]
输出: [1,2]

提示:

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

**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

题解 (Rust)

1. 题解

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()
    }
}