关小刷刷题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)。

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-09-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

C++STL之整理算法

这里主要介绍颠倒、旋转、随机排列和分类4中常见的整理算法 1、颠倒(反转) void reverse(_BidIt _First, _BidIt _Last) ...

21260
来自专栏take time, save time

编程一样可以很带感--1+1不一定等于“2”

刚玩了两把flash小游戏,我也不知道为什么我从小就喜欢玩这个东西,想当初我上大学选软件的目的就是为了学会做flash,那时目的单纯吧?哈哈,初中的时候看的...

37060
来自专栏HansBug's Lab

3522: [Poi2014]Hotel

3522: [Poi2014]Hotel Time Limit: 20 Sec  Memory Limit: 128 MB Submit: 253  Solve...

24960
来自专栏数据结构与算法

NOIP复习内容

https://www.luogu.org/problemnew/lists?name=GSS&orderitem=pid&tag=&content=0&typ...

18520
来自专栏编程之旅

算法时间复杂度

很多程序员,做了很长时间的编程工作却始终都弄不明白算法的时间复杂度的估算,这是很可悲的一件事情。因为弄不清楚,所以也就从不深究自己写的代码是否效率底下,是不是可...

9210
来自专栏小L的魔法馆

第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛--I-填空题

35050
来自专栏钱塘大数据

风靡全球的15则数学动图,让你秒懂数学概念

首先,把圆解剖为一个三角形。底边是周长。然后根据三角形的面积推出圆的面积,so easy~

11730
来自专栏专知

【LeetCode】关关的刷题日记23——Leetcode 66. Plus One

关小刷刷题 23——Leetcode 66. Plus One 题目 Given a non-negative integer represented as a...

30130
来自专栏小樱的经验随笔

令人称奇的简单证明:五种方法证明根号2是无理数

令人称奇的简单证明:五种方法证明根号2是无理数     我喜欢各种各样的证明。人们很难想到这样一些完全找不到突破口的东西竟然能够证明得到。说“没有突破口”还不够...

29580
来自专栏数据科学与人工智能

【机器学习】如何向外行解释机器学习和数据挖掘

对于那些非计算机科学行业的人,你会如何向他们解释机器学习和数据挖掘? 斯坦福大学的印度学生、机器学习爱好者 Pararth Shah 在2012年12月22日的...

30680

扫码关注云+社区

领取腾讯云代金券