Leetcode题解剑指 Offer 39. 数组中出现次数超过一半的数字

PROBLEM

难度简单

MY ANSWER

哈希表储存元素个数，超过一半时返回。时间空间复杂度都为O(n)。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> ht;
        for(int i = 0; i < nums.size(); i++) {
            if(ht.find(nums[i]) != ht.end()) {
                ht[nums[i]]++;
                if(ht[nums[i]] > nums.size() / 2) {
                    return nums[i];
                }
            }
            else {
                ht[nums[i]] = 1;
            }
        }
        return nums[0];
    }
};

BETTER SOLUTION

摩尔投票法，根本思想是相互抵消，最终剩下的元素就是比一半多的元素。空间复杂度降到O(1)。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
};

SUMMARY

重点掌握摩尔投票法的代码。