剑指Offer39:数组中出现次数超过一半的数字

淡淡的烟草味﹌ 2022-04-25 02:36 146阅读 0赞

题目就是从一个数组中找到其中一个值其个数超过数组的一半、

定义一个int result,int times次数,因为如果存在一个值超过数组长度的一半，那么times必定为1

首先 result = nums\[0\],times = 1;

然后从1开始循环数组,判断if(times==0)如果为0就result = nums\[i\],times =1.再判断result = nums\[i\]相等就times++，不等就--，

但是times刚开始从0开始，拿到第一个数就times = 1,所以到下一个数的时候，times要么++,--，要么为1，所以times保证了数组中的值在times都会被取到，那么一个连续的值被result拿到之后相应的times也会被加到一定的数量，而times只会被到减到0,result才会被重新赋值，以及times置1，而那个被查找的元素，个数一定是大于数组的一半，所以times最后一定不是0.相应的result就会为最多的那个数。

代码

public int Half(int[] nums){
    
            int result = nums[0];
    
            int times = 1;
    
            int length = nums.length;
    
            for(int i=1;i<length;i++){
    
                if(times==0){
    
                    result = nums[i];
    
                    times = 1;
                }else if(result==nums[i]){
    
                    times++;
    
                }else{
    
                    times--;
                }
    
    
    
            }
            return result;
        }
    
    
        public static void main(String[] args) {
    
            int[] nums = {1,2,3,2,2,2,5,4,2};
    
            System.out.println(new LookforNunbersHalf().Half(nums));
        }