专栏首页尾尾部落[剑指offer] 数组中出现次数超过一半的数字

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

题目描述

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

解题思路

三种解法:

  • 法1:借助hashmap存储数组中每个数出现的次数,最后看是否有数字出现次数超过数组长度的一半;
  • 法2:排序。数组排序后,如果某个数字出现次数超过数组的长度的一半,则一定会数组中间的位置。所以我们取出排序后中间位置的数,统计一下它的出现次数是否大于数组长度的一半;
  • 法3:某个数字出现的次数大于数组长度的一半,意思就是它出现的次数比其他所有数字出现的次数和还要多。因此我们可以在遍历数组的时候记录两个值:1. 数组中的数字;2. 次数。遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;若次数为0,则保存下一个数字,并将次数置为1。遍历结束后,所保存的数字即为所求。最后再判断它是否符合条件。

参考代码

法1:

import java.util.HashMap;
import java.util.Map;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int length = array.length;
        for(int i=0; i<length; i++){
            if(!map.containsKey(array[i]))
                map.put(array[i], 1);
            else
                map.put(array[i], map.get(array[i])+1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue()*2>length)
                return entry.getKey();
        }
        return 0;
    }
}

法2:

import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        int half = array.length/2;
        int count = 0;
        for(int i=0; i<array.length; i++){
            if(array[i] == array[half])
                count ++;
        }
        if(count > half)
            return array[half];
        else
            return 0;
    }
}

法3:

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int res = array[0], count = 1;
        for(int i=1; i<array.length; i++){
            if(array[i] == res)
                count++;
            else{
                count--;
            }
            if(count == 0){
                res = array[i];
                count = 1;
            }
        }
        count = 0;
        for(int i=0; i<array.length; i++){
            if(array[i] == res)
                count++;
        }
        return count > array.length/2 ? res : 0;
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 实现 | 朴素贝叶斯模型算法研究与实例分析

    构建一个快速过滤器来屏蔽在线社区留言板上的侮辱性言论。如果某条留言使用了负面或者侮辱性的语言,那么就将该留言标识为内容不当。对此问题建立两个类别: 侮辱类和非侮...

    伏草惟存
  • 深度 | 朴素贝叶斯模型算法研究与实例分析

    本节介绍朴素贝叶斯分类算法模型在中文领域中的应用。我们对新闻语料进行多文本分类操作,本文选择艺术、文学、教育、哲学、历史五个类别的训练文本,然后采用新的测试语料...

    伏草惟存
  • ZooKeeper典型应用场景一览(转)

    ZooKeeper是一个高可用的分布式数据管理与系统协调框架。基于对Paxos算法的实现,使该框架保证了分布式环境中数据的强一致性,也正是基于这样的特性,使得Z...

    会跳舞的机器人
  • 暗通道去雾算法原理及实现

    基本原理来源于何凯明大神的CVPR09的论文Single Image Haze Removal Using Dark Channel Prior

    和蔼的zhxing
  • 一个随机播放的算法II

    音乐时光? 骑着车,戴着耳机,播放列表里有几首歌。 突然,很想听《且听风吟》,但是不想掏出手机,于是一路双击耳机播放键切歌。 emmm,下面是切过的歌:

    冰之角
  • 亚像素数值极值检测算法总结

    在计算机视觉领域,经常需要检测极值位置,比如SIFT关键点检测、模板匹配获得最大响应位置、统计直方图峰值位置、边缘检测等等,有时只需要像素精度就可以,有时则需要...

    李拜六不开鑫
  • 伪随机数生成算法

    伪随机数生成算法在计算机科学领域应用广泛,比如枪击游戏里子弹命中扰动、数据科学里对样本进行随机采样、密码设计、仿真领域等等,背后都会用到伪随机数生成算法。

    李拜六不开鑫
  • 排序算法

    ppjun
  • 吴恩达深度学习笔记 3.1~3.11 浅层神经网络

    神经网络的结构与逻辑回归类似,只是神经网络的层数比逻辑回归多了一层,多出的中间一层叫隐藏层,那么,神经网络的计算就相当于多进行一次逻辑回归的计算

    Dar_Alpha
  • 理论 | 朴素贝叶斯模型算法研究与实例分析

    朴素贝叶斯是一种构建分类器的简单方法。该分类器模型会给问题实例分配用特征值表示的类标签,类标签取自有限集合。所有朴素贝叶斯分类器都假定样本每个特征与其他特征都不...

    伏草惟存

扫码关注云+社区

领取腾讯云代金券