leetcode 169. Majority Element 摩尔投票法

野性酷女 2022-06-08 07:28 175阅读 0赞

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.

就是使用HashMap直接计数。

代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    public class Solution {
        public int majorityElement(int[] nums) 
        {
            Map<Integer, Integer> map=new HashMap<Integer, Integer>();
            for(int i=0;i<nums.length;i++)
                map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
    
            for (Integer key : map.keySet()) 
            {  
                if(map.get(key) >= (nums.length+1)/2)
                    return key;
            } 
            return 0;
        }
    }

下面是C++的做法，就是使用map做一次遍历操作

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    #include <map>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int majorityElement(vector<int>& nums)
        {
            map<int, int> mmp;
            for (int a : nums)
            {
                if (mmp.find(a) == mmp.end())
                    mmp[a] = 1;
                else
                    mmp[a] += 1;
            }
    
            for (map<int, int>::iterator i = mmp.begin(); i != mmp.end(); i++)
            {
                if (i->second >= (nums.size() + 1) / 2)
                    return i->first;
            }
            return 0;
        }
    };

其实这道题考察的是摩尔投票法，代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    class Solution
    {
    public:
        int majorityElement(vector<int>& nums)
        {
            int count = 0, num = INT_MIN;
            for (int i : nums)
            {
                if (count == 0)
                {
                    count = 1;
                    num = i;
                }
                else if (i == num)
                    count++;
                else
                    count--;
            }
            return num;
        }
    };