题解 | #数组中出现次数超过一半的数字#

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

https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163

使用摩尔选举,遇到与res一致的,就增加num;反之,减少num

如果,num = 0,那么就更新res为当前的数组值。

public class Solution {
    public int MoreThanHalfNum_Solution(int[] array) {
        // 使用摩尔选举
        int res = array[0], num = 0;
        for (int i = 0; i < array.length; ++i) {
            if (num == 0) {
                res = array[i];
                num++;
            } else if (array[i] == res) {
                num++;
            } else {
                num--;
            }
        }
        return res;
    }
}

全部评论

相关推荐

宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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