LeetCode-剑指39-数组中出现次数冲过一半的数字

具体思路同LeetCode-169，此处我们仅讨论时间复杂度为$O(n)$的方法。

1、哈希算法

我们利用哈希表记录每个数字出现的次数，最终遍历哈希表找到出现次数最多的数字即可。时间复杂度为$O(n)$，空间复杂度为$O(n)$。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2、投票算法$$

我们可以假设$nums[0]$是数组中的多数元素，我们记录当前多数元素出现的次数$count=0$。每当我们读入一个新数字时，若他与我们假定的多数元素相同则$count+1$，否则$count-1$。当此时$count<0$时，我们将读入的新元素作为新的多数元素并重复执行上述操作。这样当我们遍历完数组时，$count$一定大于0，此时的多数元素即为最终的多数元素。该方法的时间复杂度为$O(n)$，空间复杂度为$O(1)$。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
            int count = 0;
            for (int num : nums) {
                if (num == candidate)
                    ++count;
                else if (--count < 0) {
                    candidate = num;
                    count = 1;
                }
            }
            return candidate;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17