剑指offer(28)数组中出现次数超过一半的数字

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int candidate = 0;//候选
        int count = 0;//次数
        for(int i = 0;i != array.length;i++){//核心代码:一次在数组中删掉两个不同的数字,不停的删除直到剩下的数只有一种,如果一个数字出现的次数大于一半,则这个数字一定会被剩下来,也就是最后的candidate值
            if(count == 0){
                candidate = array[i];
                count = 1;
            }else if(array[i] == candidate){
                count++;
            }else{
                count--;
            }
        }
        
        count = 0;
        for(int i = 0;i != array.length;i++){//如果是1,2,3,3会被剩下,这个for则检验剩下的数字出现的次数是否过半
            if(array[i] == candidate){
                count++;
            }
        }
        if(count > array.length / 2){
           return candidate;
        }else{
           return 0;
        }
     
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 11:35
程序员小白条:话太多,没实力和学历,差不多回答回答就行了,身份地位不一样
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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