169.md

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.

思路

解法1

创建一个map<int,int> mp;建立数值和出现次数的对应关系。遍历一边给定的nums，对于每一个值nums[i]如果mp中找不到nums[i],则初始化为1，否则
对mp[nums[i]]++;如果mp[nums[i]]>nums.size()/2，则nums[i]就是majority element。

解法2

由于问题中majority element总是大于nums.size()/2,所以对于问题的开始，假设nums[0]为majority element，如果nums[0]!=nums[1]
则问题简化为少了索引0和1的nums中寻找majority element，因为如果nums[0]是majority element则nums[1]不是，则两个元素同时出去
变为子问题对结果不影响，如果nums[0]不是majority element，nums[1]也不是，也不会影响，如果nums[0]不是nums[1]是也不影响。

代码

解法1

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> mp;
        int n = nums.size();
        int times = n / 2;
        for(int i=0;i<n;++i){
            if(mp.find(nums[i])==mp.end()){
                mp[nums[i]] = 0;
            }
            mp[nums[i]]++;
            if(mp[nums[i]]>times) return nums[i];
        }
    }
};

解法2

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n=nums.size();
        int count =0,majority=0;
        for(int i=0;i<n;++i){
            if(count==0) majority = nums[i];
            if(nums[i]==majority) ++count;
            else --count;
        }
        return majority;
    }
};