# 169. Majority Element - LeetCode 原

yysue

## Question

169. Majority Element

## Solution

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.

### 评论(2)

#### 引用来自“yysue”的评论

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

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

Quincuntial
2017/03/15
0
0

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

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

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 的区别

22分钟前
1
0

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

mylxsw
27分钟前
0
0
mybatis3-javaapi

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