LeetCode #169. Majority Element 数组 摩尔投票法

Description

---

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

思路

---

解法一

纯暴力，使用一个哈希 map 记录数据出现的个数，遍历数组，当符合 majority element 的元素出现时就 return。

时间复杂度：O(n)
空间复杂度：O(n)

耗时 24 ms, Memory 9.1 MB, ranking 51%

class Solution {
public:
    int majorityElement(const vector<int> &nums) {
        unordered_map<int, int> m;  // mapping from a number to times that it appears
        
        int mj_element = nums[0];
        for (int i = 0; i < nums.size(); ++i) {
            auto iter = m.find(nums[i]);
            if (iter == m.end()) {
                m[nums[i]] = 1;
            } else {
                iter->second += 1;
                
                if (iter->second > nums.size()/2) {  // find the majority element
                    mj_element = iter->first;
                    break;
                }
            }
        }
        
        return mj_element;
    }
};

解法二

Moore Voting 算法，使用该算法的前提是数组必须存在一个 majorityElement 且它的出现频数大于数组元素数目的一半。

时间复杂度：O(n)
空间复杂度：O(1)

耗时 16 ms, Memory 8.8 MB, ranking 95.6%

class Solution {
public:
    int majorityElement(const vector<int> &nums) {
        int mj_element = nums[0];  // candidate in Moore Voting algorithm
        int count = 1;  // counter in Moore Voting algorithm

        for (int i = 1; i < nums.size(); ++i) {
            if (mj_element == nums[i]) {
                ++count;
            } else {
                --count;

                if (!count) {
                    mj_element = nums[i];
                    count = 1;
                }
            }
        }

        return mj_element;
    }
};

参考

---

• 《[LeetCode] 169. Majority Element 求大多数》：https://www.cnblogs.com/grandyang/p/4233501.html