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

摩尔投票法

摩尔投票法：摩尔投票法的核心思想为对拼消耗

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function (nums) {
    // 摩尔投票法
    // 找出数组中元素出现过的次数 > 数组长度/3 的元素
    // 1/2 至多出现1个
    // 1/3 至多出现2个
    // 1/m 至多出现 m-1 个

    let ele1 = nums[0]
    let ele2 = nums[0]
    let vote1 = 0
    let vote2 = 0

    for (let num of nums) {
        if (num === ele1) {
            vote1++
            continue
        }
        if (num === ele2) {
            vote2++
            continue
        }

        if (vote1 === 0) {
            ele1 = num
            vote1++
            continue
        }
        if (vote2 === 0) {
            ele2 = num
            vote2++
            continue
        }

        vote1--
        vote2--

    }

    let count1 = 0
    let count2 = 0

    for (let num of nums) {
        if (num === ele1) {
            count1++
        }
        if (num === ele2) {
            count2++
        }
    }

    let ans = []
    if (vote1 > 0 && count1 > nums.length / 3) {
        ans.push(ele1)
    }
    if (vote2 > 0 && count2 > nums.length / 3) {
        ans.push(ele2)
    }

    return ans
};

哈希统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function (nums) {
    const countMap = new Map()
    for (let num of nums) {
        if (countMap.has(num)) {
            countMap.set(num,countMap.get(num) + 1)
        } else {
            countMap.set(num, 1)
        }
    }

    const ans = []
    for (let num of countMap.keys()) {
        if (countMap.get(num) > (nums.length / 3)) {
            ans.push(num)
        }
    }
    return ans
};