数组中出现次数超过一半的数字Java

数组中出现次数超过一半的数字

http://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163

采用阵地攻守的思想:
1,在遍历数组的时候保存两个值:一个是数组中的一个数字,一个是次数。
2,当我们遍历到下一个数字的时候,如果下一个数字和当前我们保存的数字相同,则次数加 1;
如果和当前我们保存的数字不同,则次数减 1;
当次数减到 0 的时候,我们将保存的数字改为当前遍历所处的位置,并将次数更改为 1。
3,最后当times>1,说明当前的num出现的次数超过一半

public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {

if(array.length==0){
        return 0;
    }

    int times = 1;
    int num = array[0];
    for(int i=0; i<array.length;i++){

        if(num == array[i]){
            times++;
        }else{
            times --;
            if(times == 0){
            num = array[i];
              times =1;
         }
        }

    }
    if(times>1){
        return num;
    }else{
         return 0;

    }

}

}

全部评论

相关推荐

牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务