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

小咪咪 2022-12-28 00:59 117阅读 0赞

> [剑指Offer 39 数组中出现次数超过一半的数字 \[easy\]][Offer 39 _ _easy]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 一、题解1 ###

##### 1. 思路：hash字典 #####

1.  hash 字典统计数量，数量大于数组长度一半时返回结果

##### 2. 时间复杂度：O(n) #####

##### 3. 空间复杂度：O(n) #####

### 二、题解2 ###

##### 1. 思路：排序 #####

1.  排序
2.  **排序后的中位数一定是的结果**

##### 2. 时间复杂度：O(nlogn) #####

##### 3. 空间复杂度：O(logn) 排序递归栈空间 #####

##### 4. 实现 #####

/** * @param {number[]} nums * @return {number} */
    var majorityElement = function(nums) { 
        nums.sort((a, b) => a - b);
        return nums[Math.floor(nums.length / 2)];
    };

### 三、题解3 ###

##### 1. 思路：摩尔投票法（Boyer-Moore） #####

1.  **前提：目标数的数量大于数组长度的一半**
2.  每一个目标数与其他如何非目标数抵消，最终剩下的一定是目标数

##### 2. 步骤 #####

![在这里插入图片描述][2020121311374627.gif]

> 补充
> 
>  *  当votes变为0时，若上一轮假设的众数是目标数，则其他数与目标数**消耗的数量一致**，剩下的数字中**目标数数量依旧大于一半**
>  *  若上一轮假设的众不是目标数，则**目标数消耗数量小于其他数**，剩下的数字中**目标数数量依旧大于一半**

##### 3. 时间复杂度：O(n) #####

##### 4. 空间复杂度：O(1) #####

##### 5. 实现 #####

/** * @param {number[]} nums * @return {number} */
    var majorityElement = function(nums) { 
        // 预处理（无）
    
        // 摩尔投票法
        let curr = nums[0], vote = 1;
        for(let i=1, len=nums.length; i<len; i++){ 
            if(vote === 0) curr = nums[i];
            if(nums[i] === curr) vote++;
            else vote--;
        }
    
        // 返回
        return curr;
    };

### 四、题解4 ###

##### 1. 思路：位运算 #####

1.  目标数数量大于数组长度的一半，相应的，该目标数的二进制数中，每一位(1 / 0)的数量也大于数组长度的一半

[Offer 39 _ _easy]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/bd159325274245ca9e2a3ed8163e3c72.png
[2020121311374627.gif]: https://img-blog.csdnimg.cn/2020121311374627.gif