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
Leetcode 169. Majority Element

SnailTyan
09/13
0
0
LeetCode 169. Majority Element - majority vote algorithm (Java)

1. 题目描述Description Link: https://leetcode.com/problems/majority-element/description/ Given an array of size n, find the majority element. The majority element is the elemen......

rgvb178
2017/12/12
0
0
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
438. Find All Anagrams in a String - LeetCode

Question 438. Find All Anagrams in a String Solution 题目大意：给两个字符串，s和p，求p在s中出现的位置，p串中的字符无序，ab=ba 思路：起初想的是求p的全排列，保存到set中，遍历s，如...

yysue
07/17
0
0

qq_32690999
01/25
0
0

Java3y
12分钟前
0
0
nginx的一些总结

Linux下安装Nginx完整教程及常见错误解决方案 1.Nginx安装环境 Nginx是C语言开发,建议在linux上运行,本教程使用Centos7.0作为安装环境. 1)gcc 安装nginx需要先将官网下载的源码进行编译，编译...

Yao--靠自己
19分钟前
0
0
Predicate函数式接口

Predicate接口主要用于流的筛选，比如在filter方法中传入Predicate判断。 作为函数式接口，这里居然有三个default方法，一个static方法，子孙满堂！ 正统的接口方法，就是boolean test(T t)...

woshixin
20分钟前
0
0
sql 开窗函数

hblt-j
30分钟前
1
0

38分钟前
1
0