文档章节

169. Majority Element - LeetCode

yysue
 yysue
发布于 06/21 22:29
字数 374
阅读 15
收藏 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
粉丝 25
博文 255
码字总数 149514
作品 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......

~yzhu
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

没有更多内容

加载失败,请刷新页面

加载更多

web打印控件 LODOP的详细api

web打印控件 LODOP的详细api

wangxujun59
55分钟前
3
0
从一次小哥哥与小姐姐的转账开始, 浅谈分布式事务从理论到实践

分布式事务是个业界难题,在看分布式事务方案之前,先从单机数据库事务开始看起。 什么是事务 事务(Transaction)是数据库系统中一系列操作的一个逻辑单元,所有操作要么全部成功要么全部失...

中间件小哥
58分钟前
6
0
荣登Github日榜!微信最新开源MMKV

MMKV 开源当日即登Github Trending日榜,三日后荣登周榜。MMKV 在腾讯内部开源半年,得到公司内部团队的广泛应用和一致好评。 MMKV 是基于 mmap 内存映射的移动端通用 key-value 组件,底层序...

腾讯开源
今天
5
0
前端取色工具:jcpicker

http://annystudio.com/software/colorpicker/#jcp-download

轻量级赤影
今天
1
0
Swift - 将图片保存到相册

import Photos func loadImage(image:UIImage) { UIImageWriteToSavedPhotosAlbum(image, self, #selector(saveImage(image:didFinishSavingWithError:contextInfo:)), ni......

west_zll
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部