数组中出现次数超过一半的数字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;

    }

}

}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 13:32
点赞 评论 收藏
分享
码砖:求职岗位要突出,一眼就能看到,教育背景放到最后,学校经历没那么重要,项目要重点突出
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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