文档章节

169. Majority Element - LeetCode

yysue
 yysue
发布于 06/21 22:29
字数 374
阅读 20
收藏 0

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
粉丝 27
博文 268
码字总数 155357
作品 0
济南
程序员
私信 提问
加载中

评论(2)

yysue
yysue

引用来自“yysue”的评论

1
2111
yysue
yysue
1
Leetcode 169. Majority Element

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/82693029 文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Descr...

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
决战Leetcode: easy part(1-50)

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

qq_32690999
01/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

我是如何将博客转成PDF的

前言 只有光头才能变强 之前有读者问过我:“3y你的博客有没有电子版的呀?我想要份电子版的”。我说:“没有啊,我没有弄过电子版的,我这边有个文章导航页面,你可以去文章导航去找来看呀”...

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 开窗函数

开窗函数:在开窗函数出现之前存在着很多用 SQL 语句很难解决的问题,很多都要通过复杂的相关子查询或者存储过程来完成。为了解决这些问题,在 2003 年 ISO SQL 标准加入了开窗函数,开窗函数...

hblt-j
30分钟前
1
0
使用Vue动态生成form表单的实例代码

具有数据收集、校验和提交功能的表单生成器,包含复选框、单选框、输入框、下拉选择框等元素以及,省市区三级联动,时间选择,日期选择,颜色选择,文件/图片上传功能,支持事件扩展。 欢迎大家s...

嫣然丫丫丫
38分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部