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;
    }
};


参考



上一篇:1 MW/60 MJ飞轮储能系统轴系动力学分析与试验研究


下一篇:[C/C++游戏编码教程]:扫雷游戏