作者：whisper

链接：https://www.proprogrammar.com/article/912

声明：请尊重原作者的劳动，如需转载请注明出处

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：

1 <= 数组长度 <= 50000

难度：简单；标签：位运算，分治算法；编程语言：JAVA

其它解法

class Solution {
    // 题解中的一个比较好的方法
    // https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/onshi-jian-fu-za-du-o1kong-jian-fu-za-du-zhao-chu-/
    public int majorityElement(int[] nums) {
        int count = 1;
        int res = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == res){
                count++;
            }else{
                count--;
                if(count < 0){
                    count = 1;
                    res = nums[i];
                }
            }
        }

        return res;
    }
}

自己想不到时间复杂度O(n)的解法，看一下题解中的解法，计数，遇到res结果数+1，其它数-1（抵消），当res<0时，重新计数，因为最终结果出现次数大于一半，所以最坏的情况下，最终结果的count也是大于0的，对其它的数，遇到不同的-1，肯定会减成<0，也就是说其它数会减成<0，而最终结果不论如何减，最终count都是大于0的，所以是可以的

亲爱的读者：有时间可以点赞评论一下