Leetcode-Array-169.多数元素

发表于 更新于 分类于 ， 阅读次数： 本文字数： 217 阅读时长 ≈ 1 分钟

https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

思路

主要有以下几种思路，因为我曾经似乎遇到过，所以很快直接想到了最佳算法。

  1. 统计数量，采用哈希表存储会比较好
  2. 排序后取中间位置
  3. 随机算法，不稳定算法
  4. Boyer-Moore 投票算法，简单来说就是消消乐，遇到和当前候选数相同的，计数值加一，不同则减一，变为0时若遇到新的数，更换候选数。

代码

代码很简单，就不需要伪代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    // 这道题目我有些印象，遇到不同的直接消除即可
    public int majorityElement(int[] nums) {
        int num=0;
        int maj=nums[0];
        for(int i=0;i<nums.length;i++)
        {
            if(num==0){
                maj=nums[i];
                num++;
            }else if(maj==nums[i]){//num!=0
                num++;
            }else{ // num!=0 and  maj!=nums[i]
                num--;
            }
        }
        return maj;

    }
}