题目

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

解题思路

思路一：哈希统计

对数组进行遍历，使用map对所有的数值进行统计；然后再对map进行遍历找出符合题目要求的数值。
时间复杂度O(n)，空间复杂度O(n)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    let count = new Map();
    for(let i=0;i<nums.length;i++){
        if(count.has(nums[i])){
            count.set(nums[i],count.get(nums[i])+1);
        }else{
            count.set(nums[i],1);
        }
    }
    let result =[];
    for(const x of count.keys()){
        if(count.get(x)>parseFloat(nums.length/3)){
            result.push(x);
        }
    }
    return result;
};

思路二：摩尔投票法

  摩尔投票法：简单来说，该方法是为了解决如何在人一多的候选人中，选出票数超过一半的那个人，我们可以直接利用反证法证明这样的数字只可能有一个。时间复杂度O(n)，空间复杂度O(1)。算法分为两个阶段：抵消阶段和计数阶段
  举个例子：假设投票结果如下：[a,c,c,a,a,b,a]，a,b,c为三个候选人。摩尔投票法的思路如下:
  首先选择第一张票a作为候选人，同时设置计数值vote=1，接着第一张票与第二张票进行比较，如果相同vote加一，不相同a_vote减一；
  接着与第三张票进行比较，结果不相同，但此时a_vote为0，故需要更换待定人为对应票面候选人c，并且将vote=1；接着与第四张票进行比较，结果不同vote减一；
  接着继续比较第五张票，结果不相同进行更换为a，vote=1；
  与第六张票进行比较，不同vote减一；
  与第七张票进行比较相同加一；
  得到最终结果为：候选人a，vote=1；
  如果得到的结果vote为0，那他已经无缘票数能超过一半的那个人了，直接返回结果；
  如果最后得到的抵消票数不为 0 的话，那说明他可能希望的，这是我们需要一个阶段来验证这个候选人的票数是否超过一半——计数阶段；
=====================================================
  回到本题，我们可以利用升级版的摩尔投票法来达到目的，我们可以利用反证法推断出满足这样条件的元素最多只有两个，同样我们做以下假设：假设投票结果如下[a,b,c,a,a,b,c]，abc是三个候选人。
  此时我们选择两个候选人分别定义为：x,y;对应的抵消票为x_vote,y_vote;
  现在开始抵消：首先将第一张票x=a，x_vote=1，第二张票将y=b，y_vote=1;
  第三张票，x，y与之都不相同各自vote都减一，此时：x=a，x_vote=0；y=b，y_vote=0；
  第四张票，x与之相同，但此时x_vote和y_vote均为0，则先对x重新进行赋值，此时：x=a，x_vote=1；y=b，y_vote=0；
  第五张票，x与之相同，则x_vote加一，此时：x=a，x_vote=2；y=b，y_vote=0；
  第六张票，y与之相同，此时y=b，但y_vote=0，所以此时对y重新进行赋值，此时：x=a，x_vote=2；y=b，y_vote=1；
  第七张票，x，y与之都不相同各自vote都减一，此时：x=a，x_vote=1；y=b，y_vote=0；至此抵消阶段结束。
  接下来进行计数。由于y_vote=0，则y所对应的b候选人已经失去资格，故此时对a进行计数统计，然后判断a候选人的票数是否大于总数的三分之一。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
    let a_vote=0;
    let b_vote=0;
    let a=0;
    let b=0;

    for(let i=0;i<nums.length;i++){
        if(a==nums[i]&&acount>0){
            a_vote++;
        }else if(b==nums[i]&&bcount>0){
            b_vote++;
        }else if(acount==0){
            a = nums[i];
            a_vote++;
        }else if(bcount==0){
            b = nums[i];
            b_vote++;
        }else{
            a_vote--;
            b_vote--;
        }
    }
    let total_a=0;
    let total_b=0;
    let result=[];
    for(let i=0;i<nums.length;i++){
        if(a_vote>0&&a==nums[i]){
            total_a++;
        }else if(b_vote>0&&b==nums[i]){
            total_b++;
        }
    }
    if(a_vote>0&&total_a>parseFloat(nums.length/3)){
        result.push(a);
    }
    if(b_vote>0&&total_b>parseFloat(nums.length/3)){
        result.push(b);
    }
    return result;
};