面试题 17.10. 主要元素【Boyer-Moore 投票算法】

不念不忘少年蓝@ 2022-10-19 05:33 155阅读 0赞

[Boyer-Moore 投票算法][Boyer-Moore]

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        int majorityElement(vector<int>& nums) { 
            int cnt = 0;
            int cd = -1;
            for(auto& i:nums){ 
                if(cnt == 0){ 
                    cd = i;
                    cnt = 1;
                }else{ 
                    if(cd == i){ 
                        ++cnt;
                    }else{ 
                        --cnt;
                    }
                }
            }
            cnt=0;
            for(auto& i:nums){ 
                if(i==cd){ 
                    ++cnt;
                }
            }
            if(cnt*2>nums.size()){ 
                return cd;
            }
            return -1;
        }
    };

![在这里插入图片描述][20210709172850495.png]

[Boyer-Moore]: https://leetcode-cn.com/problems/find-majority-element-lcci/solution/zhu-yao-yuan-su-by-leetcode-solution-xr1p/
[20210709172850495.png]: /images/20221005/bd2455c5de894e6b97e1a3477671b6f1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，155人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】摩尔投票算法

目录 1.概述 2.算法思想 3.代码实现 3.1.t = ⌊n / 2⌋ 3.2.t = ⌊n / 3⌋ 3.

电玩女神/ 2024年02月18日 13:53/ 0 赞/ 66 阅读

相关 LeetCode_Boyer-Moore 投票算法_简单_169.多数元素

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于

水深无声/ 2023年10月06日 18:47/ 0 赞/ 54 阅读

相关算法面试题:多数元素

leetcode 面试题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是

淡淡的烟草味﹌/ 2023年07月13日 15:30/ 0 赞/ 28 阅读

相关 Leetcode-面试题 17.10. 主要元素(摩尔投票法)

面试题 17.10. 主要元素 (摩尔投票法）方法一：Map方法（不满足题目空间复杂度）方法二：摩尔投票法 > 面试题 17.10. 主要元素 >

电玩女神/ 2023年02月22日 08:06/ 0 赞/ 34 阅读

相关 LeetCode:面试题 17.10. 主要元素(C语言)

题目描述：数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。示例 1：输入：\[1,2,5,9,5,9,5,5,5\

阳光穿透心脏的1/2处/ 2023年02月21日 14:15/ 0 赞/ 29 阅读

相关多味的LeetCode --- 面试题 17.10. 主要元素

前期回顾： [面试题39. 数组中出现次数超过一半的数字][39.] 题目描述：数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回

曾经终败给现在/ 2023年01月08日 13:24/ 0 赞/ 121 阅读

相关 leetcode——面试题 17.10. 主要元素

问题描述：数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。示例 1：输入：\[1,2,5,9,5,9,5,5,5\]

骑猪看日落/ 2022年10月22日 14:59/ 0 赞/ 128 阅读

相关面试题 17.10. 主要元素

> 数组中占比超过一半的元素称之为主要元素。给你一个整数数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

电玩女神/ 2022年10月19日 05:35/ 0 赞/ 140 阅读

相关面试题 17.10. 主要元素【Boyer-Moore 投票算法】

[Boyer-Moore 投票算法][Boyer-Moore] define debug(x) cout<<x<<": "<<(x)<<endl;

不念不忘少年蓝@/ 2022年10月19日 05:33/ 0 赞/ 156 阅读

相关面试题 17.10. 主要元素【投票算法 C++】

数组中占比超过一半的元素称之为主要元素。给你一个整数数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

布满荆棘的人生/ 2022年10月19日 04:28/ 0 赞/ 141 阅读