求众数

发表于 更新于

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

1
2
输入: [3,2,3]
输出: 3

示例 2:

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

思路

常规思路,先遍历数组然后统计每个数组的元素出现的个数,然后找出个数最多的

解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
use std::collections::HashMap;

impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> i32 {
        let mut numsMap = HashMap::new();
        for num in nums {
            let count = numsMap.entry(num).or_insert(0);
            *count += 1
        }
        let mut maxValue = 0;
        let mut maxKey = 0;
        for(key, value) in numsMap {
            if value > maxValue {
                maxKey = key;
                maxValue = value;
            }
        }
        return maxKey;
    }
}

思路二: 不借用其他空间,由众数定义可知,众数出现次数大于 n/2, 则意味着 众数 m 的出现的次数 - 数组中其他数字的次数 > 0

解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> i32 {
        let mut num = 0;
        let mut count = 0;
        for i in 0..nums.len()
        {
            if(count == 0)
            {
                num = nums[i];
                count = 1;
            }
            else if nums[i] != num
            {
                count-=1;
            }
            else
            {
                count+=1;
            }
        }
        num
    }
}