剑指offer第五天

28.数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

解法一:利用HashMap

import java.util.HashMap;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int length = array.length;
        if(length == 1) return array[0]; //此处用于当数组只有一个元素的时候,下面的代码对该情况无效
        for(int i : array){
           if(map.containsKey(i)){
               if(map.get(i) == length/2)
                   return i;
               map.put(i,map.get(i) + 1);
               
           }else{
               map.put(i,1);
           }
        }
        return 0;
    }
}

解法二:利用数组特点,重复次数超过一半的数字一定大于其它数字出现次数之和

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0) return 0;
        int length = array.length;
        int result = array[0];
        int times = 1;
        for(int i =1;i<length;i++){
            if(result == array[i])
                times++;
            else if(times == 0){
                result = array[i];
                times =1;
            }else
                times--; 
        }
        if(times == 0) return 0;
        times = 0;
        for(int i =0;i<length;i++){
            if(array[i] == result)
                times++;
        }
        if(times <= length/2)
            result = 0;
        return result;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LanceToBigData

JavaSE(八)之Collection总结

  前面几篇把集合中的知识大概都详细的说了一遍,但是我觉得还是要总结一下,这样的话,可以更好的理解集合。 一、Collection接口 首先我们要一张图来说明:...

2466
来自专栏Hongten

python开发_类型转换convert

E | hongtenzone@foxmail.com  B | http://www.cnblogs.com/hongten

1702
来自专栏一个会写诗的程序员的博客

第7章 集合类第7章 集合类

在 Java 类库中有一套相当完整的容器集合类来持有对象。Kotlin没有去重复造轮子(Scala则是自己实现了一套集合类框架),而是在Java 类库的基础上进...

822
来自专栏微信公众号:Java团长

Java 类集框架(Set, List, Map)的使用

Set 接口和 List 接口都是 Collection 的子接口,因此我们先看看Collection 接口中有什么方法:

1192
来自专栏lgp20151222

java中两个map比较

1322
来自专栏青玉伏案

JavaSE高级之集合类

​下面的内容是对java中的集合类进行的总结,过段时间会分享java的网路编程,多线程等内容,欢迎批评指正。 1.Java中的集合是用来存放对象的,即集合是对象...

2429
来自专栏鸿的学习笔记

Python和Scala的集合和映射

在入门系列的最后,让我们来看看基于hash表的两种常见的数据结构,集合和映射。在Scala里的集合和映射,这两种数据结构都有可变和不可变的两种版本,区别仅仅在于...

692
来自专栏闻道于事

Java之集合初探(一)

一、集合概述、区别 集合是一种容器,数组也是一种容器 在Java编程中,装各种各样的对象(引用类型)的叫做容器。 为什么出现集合类? 面向对象语言对事物的体现都...

2567
来自专栏LinkedBear的个人空间

唠唠SE的集合-02——Iterator迭代器

迭代时如果没有先执行next()则会抛出IllegalStateException,这就意味着必须要先检查是否还有下一个可以被迭代的元素,才能往外取。

1043
来自专栏java一日一条

Java面试题:如何对HashMap按键值排序

Java中HashMap是一种用于存储“键”和“值”信息对的数据结构。不同于Array、ArrayList和LinkedLists,它不会维持插入元素的顺序。

1222

扫码关注云+社区

领取腾讯云代金券