LeetCode 169 Majority Element

Posted on | In | 阅读

169 Majority Element

229 Majority Element II

摩尔投票法

摩尔投票法

可以看作同归于尽法。当选择超过半数的数的时候，每一次都选择一个数站上擂台，或者与当前擂台上的数不同，就与其同归于尽一个，最后再扫描统计一遍站在擂台上的数出现次数，若没有超过半数则不存在超过半数的数。

同理，若要寻找超过1/3的数。擂台就设为两个，同时与两个不同的数同归于尽，最后站在擂台上的两个数再分别统计次数，若超过1/3，则是要找的数。

LeetCode 169 Majority Element

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n % 2 == 0:
            half = n // 2
        else:
            half = n // 2 + 1
        cnt = {}
        for i in range(n):
            if not cnt.has_key(nums[i]):
                cnt[nums[i]] = 1
            else:
                cnt[nums[i]] += 1
            if cnt[nums[i]] >= half:
                return nums[i]

LeetCode 229 Majority Element II

C++ Code

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
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int tmp1, tmp2;
        int cnt1 = 0, cnt2 = 0;
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] == tmp1) {
                ++cnt1;
            }else if(nums[i] == tmp2) {
                ++cnt2;
            }else if(cnt1 == 0) {
                tmp1 = nums[i];
                cnt1 = 1;
            }else if(cnt2 == 0) {
                tmp2 = nums[i];
                cnt2 = 1;
            }else {
                --cnt1;
                --cnt2;
            }
        }
        cnt1 = 0;
        cnt2 = 0;
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] == tmp1) {
                ++cnt1;
            }else if(nums[i] == tmp2) {
                ++cnt2;
            }
        }
        vector<int> res;
        if(cnt1 > nums.size() / 3) {
            res.push_back(tmp1);
        }
        if(cnt2 > nums.size() / 3) {
            res.push_back(tmp2);
        }
        return res;
    }
};