刷脸支付 dedecms dataframe concurrency usb coreldraw入门学习 idea全局替换 磁盘清理会误删东西吗 linux重启mysql python当前日期 java变量 java日期函数 jdbc连接mysql python源码下载 xs颜色 winhex使用教程 pr黑场过渡 神魔辅助 win7仿win8主题 苹果手机怎么看内存 ps祛痘 苹果8怎么截屏 打开组策略的命令 u盘防复制 微信骰子控制 xr卡槽 cdr填充颜色 environment 千千静听老版本下载 cf活动一键领取 mysql数据库迁移 16g101图集 3dmax人物建模 ae怎么剪辑视频 mysql慢查询日志 哔哩哔哩工具箱 numpy安装教程 苹果8拆机视频 wps怎么设置背景 ps查找边缘
当前位置: 首页 > 学习教程  > 编程语言

剑指offer——数组中出现次数超过一半的数字

2020/7/24 9:23:31 文章标签:

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

题解:
第一种方法:
------哈希存储
第二种方法:
------用preValue记录上一次访问的值,count表明当前值出现的次数,如果下一个值和当前值相同那么count++;如果不同count–,减到0的时候就要更换新的preValue值了,因为如果存在超过数组长度一半的值,那么最后preValue一定会是该值。

import java.util.HashMap;
public class Solution {
    public int MoreThanHalfNum_Solution1(int [] array) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<array.length;i++){
            if(map.containsKey(array[i])){
                int newValue = map.get(array[i]) + 1;
                map.put(array[i],newValue);
            }else{
                map.put(array[i],1);
            }
        }
        
        for(int i=0;i<array.length;i++){
            if(map.get(array[i]) > array.length/2){
                return array[i];
            }
        }
        return 0;
    }
    
    
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length == 0 || array == null) return 0;
        int preValue = array[0];
        int count = 1;
        for(int i=1;i<array.length;i++){
            if(array[i] == preValue){
                count++;
            }else{
                count--;
                if(count == 0){
                    preValue = array[i];
                    count = 1;
                }
            }
        }
        
        int number = 0;
        for(int i=0;i<array.length;i++){
            if(array[i] == preValue){
                number++;
            }
            if(number > array.length/2){
                return preValue;
            }
        }
        return 0;
    }
}

本文链接: http://www.dtmao.cc/news_show_50056.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?