关关的刷题日记02 – Leetcode 169. Majority Element方法2

题目

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.

方法2：把每个数出现的次数用一个HashMap记录下来，key是数组中的数，value是该数出现的次数。因为最后想找出现次数最大的数，也就是找最大value对应的key值。时间复杂度O(n).

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int>temp;
        for(int i=0; i<nums.size(); i++)
        {
            temp[nums[i]]++;            
        }
        int number=temp.begin()->first;
        int count=temp.begin()->second;
        for(auto it=temp.begin(); it!=temp.end(); it++)
        {
            if(it->second>count)
            {
                number=it->first;
                count=it->second;
            }
        }
        return number;
}};
对上面的代码进行了优化：
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int>temp;
        for(int x:nums)
        {
            if (++temp[x]>nums.size()/2)
            {
                return x;
            }
        }
    }
};

方法3：可以采用类似于下棋对子的方法。从头开始遍历数组，只要有不一样的两个数就相互对掉，那么最后剩下的那个数就是所求解。这种方法相比于前两种方法很巧妙，最不容易想到。但是时间复杂度O(n)，相比于方法一的sort快排O(nlogn)降低了时间复杂度。不利用额外空间，相比于方法二的HashMap降低了空间复杂度。

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

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。