剑指offer系列之二十七:数组中出现次数超过一半的数

题目描述

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

思路分析:由于是一个数字,因为其次数超过1,那么其出现的出现综合肯定实际大于其他所有数字之和的。因为如此,我们可以设置一个变量用于辨识这个变量,遇到相同的数字就把次数增加1,如果没有没有遇到就把次数减少1,那么肯定次数有可能变为0,因为没有遇到相同的。因为那个数字的次数出现了超过一半,举一个极端的例子,该数字在其他数字之后连续出现,此时times变量应该是一个负值了,那么当该数字的出现次数与前面所有数字的出现次数相等的时候,times变量变为0,由于其次数超过一半,那么该变量别重新赋值为1,所以就找到了该数字。

基于这种思路,实现的代码如下(已被牛客AC):

package com.rhwayfun.offer;

public class MoreThanHalfNumber {

    /**
     * 思路分析:由于有一个数字的次数超过一半,所以那个数字
     * 肯定是最后一次吧times变量设为1对应的数字
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution(int[] array) {
        if(array == null || array.length == 0) return 0;
        int times = 1;
        int result = array[0];
        for (int i = 1; i < array.length; i++) {
            if(times == 0){
                result = array[i];
                times = 1;
            }else if(array[i] == result){
                //遇到相同的数字次数就增加1
                times++;
            }else{
                //没有遇到相同的就把次数减小1
                times--;
            }
        }
        if(!checkMoreThanHalfNum(array,result)) return 0;
        return result;
    }

    /**
     * 检查该数字是否出现的次数超过一半
     * @param array
     * @param result
     * @return
     */
    private boolean checkMoreThanHalfNum(int[] array, int result) {
        int times = 0;
        for (int i = 0; i < array.length; i++) {
            if(array[i] == result){
                times++;
            }
        }

        boolean isMoreThanHalf = true;
        if(times * 2 <= array.length){
            isMoreThanHalf = false;
        }
        return isMoreThanHalf;
    }

    public static void main(String[] args) {
        int[] array = new int[]{1,2,3,2,2,2,5,4,2};
        int a = new MoreThanHalfNumber().MoreThanHalfNum_Solution(null);
        System.out.println(a);
    }
}
上一篇:查找两个整型数组的公共元素


下一篇:在交付的实验环境中对许可证过期问题的虚拟机关机问题的解决方法