Welcome everyone

每周一练(28)

每周一练 汪明鑫 180浏览 0评论

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

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

 

抵消法:

如果有大于一半的数,抵消到最后剩下的数即为所求

用preValue记录上一次访问的值,count表明当前值出现的次数,如果下一个值和当前值相同那么count++;

如果不同count–,减到0的时候就要更换新的preValue值了,因为如果存在超过数组长度一半的值,那么最后preValue一定会是该值。

 

package pers.wmx.practice;

/**
 * @author: wangmingxin03
 * @date: 2020-07-07
 */
public class MoreThanHalfNum {

    public static void main(String[] args) {
        int []arr = {1,2,3,2,2,2,5,4,2};

        int moreThanHalfNum = findMoreThanHalfNum(arr);
        System.out.println(moreThanHalfNum);
    }

    public static int findMoreThanHalfNum(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }

        int preValue = array[0];
        int count = 1;

        for (int i = 1; i < array.length ; i++) {
            if (preValue == array[i]) {
                count ++;
            } else {
                if (count == 1) {
                    preValue = array[i];
                } else {
                    count --;
                }
            }
        }

        //一一抵消,如果存在大于数组长度一半的数,最后剩下的肯定是这个

        //还需要校验一下,最终的数出现次数是否超过数组的一半
        int times = 0;
        for (int i = 0; i < array.length; i++) {
            if (preValue == array[i]) {
                times ++;
            }
        }

        if (times > array.length / 2) {
            return preValue;
        }

        return -1;
    }
}

 

 

后面的计数是很有必要的,因为上面的遍历无法保证一定出现次数超过数组长度的一半的数字

为什么不能直接用count 来判断是不是大于数组长度的一半?

比如1,2,2,2,2,2,3,4,5

得到 preValue = 2    count = 2,没办法来判断

因此需要再遍历一变,对preValue计数

 

 

转载请注明:汪明鑫的个人博客 » 每周一练(28)

喜欢 (1)

说点什么

您将是第一位评论人!

提醒
avatar
wpDiscuz