美文网首页
169. Majority Element

169. Majority Element

作者: 默写年华Antifragile | 来源:发表于2020-03-29 18:23 被阅读0次

    https://leetcode.com/problems/majority-element/

    给定一个数组,其长度为n,其中存在一个数,它出现的次数超过了n/2次,求出这个数

    分析

    从数组中同时减去两个不同的数,可以看到后面剩下的数组中,出现次数最多的数字仍然超过了 一半;
    因此可以先从数组中取一个数放到模板中,然后再拿下一个数字和模板比较,如果相同,那么模板出现的次数加1,如果不相同,把这个数字和模板数字都删掉,(删掉对于模板数字来说就是出现的次数减1),然后最后面存在的模板数字就是那个次数出现超过一半的数字;

    通俗的来讲就是两个军队打仗,假设一对一双方都会伤亡,那么最后胜利留下的肯定是人多的

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

    结果:

    Runtime: 16 ms, faster than 96.31% of C++ online submissions for Majority Element.
    Memory Usage: 9 MB, less than 100.00% of C++ online submissions for Majority Element.

    相关文章

      网友评论

          本文标题:169. Majority Element

          本文链接:https://www.haomeiwen.com/subject/dxvuuhtx.html