通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

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

61人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者: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的,所以是可以的


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

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告