关小刷刷题02——Leetcode 169. Majority Element 方法2和3

题目

169. 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.

方法2

方法2:把每个数出现的次数用一个map记录下来,key是数组中的数,value是该数出现的次数。因为最后想找出现次数最大的数,也就是找最大value对应的key值。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        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) {
        map<int, int>temp;
        for(int x:nums)
        {
            if (++temp[x]>nums.size()/2)
            {
                return x;
            }
        }
    }
};

方法3

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

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


点击专知主题Leetcode: http://www.zhuanzhi.ai/#/topic/2001901869867117。查看更多关于关关的Leetcode的刷题日记。

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


展开全文
Top
微信扫码咨询专知VIP会员