LeetCode 169. Majority Element

ShenduCC

发布于 2020-02-14 18:09:07

4070

发布于 2020-02-14 18:09:07

题意：找出数组里重复最多的元素，重复最多是指数量大于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;
        
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-01-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

count