专栏首页算法修养LeetCode 169. Majority Element

LeetCode 169. Majority Element

题目

题意:找出数组里重复最多的元素,重复最多是指数量大于n/2的,

题解:题目说一定存在答案,不用额外的内存空间,怎么做呢?其实很简单,重复最多的元素的数量大于剩下所有元素数量之和,维护一个数字count,代表数量,维护一个变量a代表重复最多的元素。遇到相同的a,count++,遇到不同的count--,那么到最后count一定是大于0的,如果count等于0的时候,a的值就要更新。最后a的值一定是答案。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
        int ans;
        int count=0;
        for(int i=0;i<nums.size();i++)
        {
            if(count==0)
            {
                ans=nums[i];
                count++;
            }
            else
            {
                if(nums[i]!=ans)
                    count--;
                else
                    count++;
            }
        }
        
        return ans;
        
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 43 Multiply Strings

    ShenduCC
  • LeetCode 216. Combination Sum III(DFS)

    题意:从1-9中选出k个数之和等于n,这个k个数不能有相同的,输出所有可能的k个数字的集合,结果也不能重复

    ShenduCC
  • HDU 5636 Shortest Path(Floyed,枚举)

    Shortest Path Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131...

    ShenduCC
  • jdk1.8u131 与jdk1.8u222 cpu获取方式的差异

    int OSContainer::active_processor_count() {

    heidsoft
  • python while语句

    py3study
  • 【PAT乙级】锤子剪刀布

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 你是一直认为 count(1) 比 count(*) 效率高么?

    有 Where 条件的 count,会根据扫码结果count 一下所有的行数,其性能更依赖于你的 Where 条件,所以文章我们仅针对没有 Where 的情况进...

    Fayson
  • 理解 React Hooks 的 Capture Value 特性

    由于刚使用 React hooks 不久,对它的脾气还拿捏不准,掉了很多次“坑”;这里的 “坑” 的意思并不是说 React hooks 的设计有问题,而是我在...

    Nealyang
  • Python 练习——计算1-2+3-4

    其实,计算正负相间的式子也很简单,只需要加上一个标记正负号的变量乘到计数器上即可。

    py3study
  • 你是一直认为 count(1) 比 count(*) 效率高么?

    MySQL count(1) 真的比 count(*) 快么? 反正同事们都是这么说的,我也姑且觉得对吧,那么没有自己研究一下究竟?如果我告诉你他们一样,你信么...

    谭庆波

扫码关注云+社区

领取腾讯云代金券