169、Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

思路

有好几种方法：

方法一：排序，取中位数，最快时间复杂度O(nlogn)

方法二：Hash投票，O(n)的时间，O(n)的空间

方法三：摩尔投票法 Moore Voting，O(n)的时间，O(1)的空间

• 先将第一个数字假设为众数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。
• 然后此时计数器的值，若为零，则将下一个值设为候选众数。以此类推直到遍历完整个数组，当前候选众数即为该数组的众数。

c++11

hash投票

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        std::unordered_map<int, int> map;
        int half = nums.size() >> 1;
        for (auto num : nums) {
            map[num]++;
            if (map[num] > half) return num;
        }
        return -1;
    }
};

ac结果

Runtime: 24 ms, faster than 61.01% of C++ online submissions for Majority Element.
Memory Usage: 11.3 MB, less than 35.84% of C++ online submissions for Majority Element.

摩尔投票

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

ac结果：

Runtime: 28 ms, faster than 42.43% of C++ online submissions for Majority Element.
Memory Usage: 11.3 MB, less than 61.73% of C++ online submissions for Majority Element.

感觉这个内存统计不是很准啊！