文档章节

169. Majority Element - LeetCode

yysue
 yysue
发布于 06/21 22:29
字数 374
阅读 11
收藏 0
点赞 0
评论 2

Question

169. Majority Element

Solution

思路:构造一个map存储每个数字出现的次数,然后遍历map返回出现次数大于数组一半的数字.

还有一种思路是:对这个数组排序,次数超过n/2的元素必然在中间.

Java实现:

public int majorityElement(int[] nums) {
    Map<Integer, Integer> countMap = new HashMap<>();
    for (int num : nums) {
        Integer count = countMap.get(num);
        if (count == null) {
            count = 0;
        }
        countMap.put(num, count+1);
    }
    for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
        if (entry.getValue() > nums.length/2) {
            return entry.getKey();
        }
    }
    return 0;
}

在讨论区看到一个创新的解法:

public int majorityElement(int[] num) {

    int major=num[0], count = 1;
    for(int i=1; i<num.length;i++){
        if(count==0){
            count++;
            major=num[i];
        }else if(major==num[i]){
            count++;
        }else count--;

    }
    return major;
}

这是讨论中对该解法的一个说明:

1)According to problem Major element appears more than ⌊ n/2 ⌋ times

2)Count is taken as 1 because 1 is the least possible count for any number ,

3)Major element is updated only when count is 0 which means --Array has got as many non major elements as major element

  1. Check this case 1,1,3,3,5,3,3 ---Majority element is 1 initially count becomes 0 at after 2nd 3 and 5 is made as majority element with count=1 and finally 3 is made as major element.

Major Element是出现次数大于n/2的一个数,遍历这个数组时,只有Major Element才能保证count>0.

© 著作权归作者所有

共有 人打赏支持
yysue
粉丝 16
博文 142
码字总数 119152
作品 0
济南
程序员
加载中

评论(2)

yysue
yysue

引用来自“yysue”的评论

1
2111
yysue
yysue
1
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 ......

Leafage_M
01/06
0
0
决战Leetcode: easy part(1-50)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
01/25
0
0
Leetcode 229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space. 题意:从数组里找出所有出现次......

ShutLove
01/25
0
0
697. Degree of an Array - LeetCode

Degree of an Array - LeetCode Question 697. Degree of an Array - LeetCode Solution 理解两个概念: 数组的度:[1,2,2,3,1]这个数组,去重后的元素为[1,2,3],每个元素在原数组中重复的次...

yysue
06/09
0
0
关于分治法的一些问题

Given an array of size n, you are required to give an algorithm to find the majority elements with the idea of divide and conquer. The majority element is the element that appea......

978326187
2017/03/05
91
1
[LeetCode] LRU Cache

The basic idea is to store the key-value pair in some container. In the following code, we make three type definitions: 1 typedef list LI;2 typedef pair PII;3 typedef unordered_......

jianchao_li
2015/08/18
0
0
LeetCode日记2

LeetCode-5 思路: (1)最后用子字符串操作返回string。 return s.substr(startpos, maxlength); (2)回文串的判断: 1)首先找出回文串中间连续的重复的字符。 2)再向两边进行判断 (3...

fxdhdu
2015/10/19
53
0
Leetcode 1——Two Sum

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 问题描述 Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may as......

Quincuntial
2017/03/15
0
0
算法解题记录——TwoSum(leetCode#1-easy)

题目 Problem Description Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exac......

三汪
2017/12/06
0
0
Leetcode日记8

(2015/2/3) LeetCode 4 Median of Two Sorted Arrays 题目大意:找到两个已排序数组的median。 median:中间位置的值。 算法: 参考:https://leetcode.com/discuss/15790/share-my-o-log...

fxdhdu
2016/02/18
94
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

垃圾回收算法

一 如何判断对象可以回收 1 引用计数法 思路大概为:给对象添加一个引用计数器,每当有一个地方引用它时,计数器值加1;当引用失效时,计数器减1;任何时刻计算器为0的对象就是不可能再被使用...

sen_ye
8分钟前
0
0
Activiti简介(学习总结一)

一、介绍 activiti是使用命令模式设计基于bpmn2.0的一款开源工作流引擎。 工作流简单举例:提交请假申请->经理审批->结束。这就是一个简单流程。activiti支持用户自定义流程。配置各个流程对...

沙shasha
8分钟前
0
0
VCL界面控件DevExpress VCL Controls发布v18.1.3|附下载

DevExpress VCL Controls是 Devexpress公司旗下最老牌的用户界面套包。所包含的控件有:数据录入,图表,数据分析,导航,布局,网格,日程管理,样式,打印和工作流等,让您快速开发出完美、...

Miss_Hello_World
10分钟前
0
0
加米谷大数据培训:云计算、大数据和人工智能之间的关系

一般谈云计算的时候会提到大数据、谈人工智能的时候会提大数据、谈人工智能的时候会提云计算……感觉三者之间相辅相成又不可分割。 一、云计算最初的目标 云计算最初的目标是对资源的管理,管...

加米谷大数据
15分钟前
1
0
java集合元素的默认大小

当底层实现涉及到扩容时,容器或重新分配一段更大的连续内存(如果是离散分配则不需要重新分配,离散分配都是插入新元素时动态分配内存),要将容器原来的数据全部复制到新的内存上,这无疑使...

竹叶青出于蓝
17分钟前
1
0
Java快速开发平台,JEECG 3.7.7闪电版本发布,增加多套主流UI代码生成器模板

JEECG 3.7.7 闪电版本发布,提供5套主流UI代码生成器模板 导读 ⊙平台性能优化,速度闪电般提升 ⊙提供5套新的主流UI代码生成器模板(Bootstrap表单+BootstrapTable列表\ ElementUI列表表单)...

Jeecg
20分钟前
0
0
export 和 module.export 的区别

在浏览器端 js 里面,为了解决各模块变量冲突等问题,往往借助于 js 的闭包把左右模块相关的代码都包装在一个匿名函数里。而 Nodejs 编写模块相当的自由,开发者只需要关注 require,exports,...

孟飞阳
22分钟前
1
0
技术教育的兴起

技术教育的兴起 作者: 阮一峰 1、 有一年,我在台湾环岛旅行。 花莲的海边,我遇到一对台湾青年夫妻,带着女儿在海滩上玩。我们聊了起来。 当时,我还在高校当老师。他们问我,是否觉得台湾...

吕伯文
23分钟前
0
0
Linux服务器下的HTTP抓包分析

说到抓包分析,最简单的办法莫过于在客户端直接安装一个Wireshark或者Fiddler了,但是有时候由于客户端开发人员(可能是第三方)知识欠缺或者其它一些原因,无法顺利的在客户端进行抓包分析,...

mylxsw
27分钟前
0
0
mybatis3-javaapi

sqlSessionFactoryBuilder->sqlSessionFactory->sqlSession<-rowbound<-resultHandler myBatis uses a Java enumeration wrapper for transaction isolation levels, called TransactionIsol......

writeademo
30分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部