LeetCode 169. Majority Element

最新推荐文章于 2023-09-02 13:02:39 发布

s_h_r

最新推荐文章于 2023-09-02 13:02:39 发布

阅读量343

点赞数

分类专栏： LeetCode 文章标签： leetcode

本文链接：https://blog.csdn.net/s_h_r/article/details/50673052

版权

LeetCode 专栏收录该内容

13 篇文章

订阅专栏

本文介绍了一种高效的算法来找出数组中出现次数超过一半的元素。该算法通过不断删除成对的不同元素，最终剩下的即为所求。这种方法相较于使用哈希映射等数据结构更为节省空间。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意：找出一个数组中出现次数大于n/2的那个元素
思路：我的思路就是用map。。。但显然是个很low的方法。网上大神的做法是删除任意两个不相同的元素，最终剩下的那个元素就是所求。

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