169.多数元素（LeeCode）

169. 多数元素

难度：简单

给定一个大小为 *n *的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

进阶：

• 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

通过次数：284,001
提交次数：431,167

这是我第一次写解题博客，之所以有感而发，也许是因为这道题算法的奇妙之处。先上代码~~~

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        if (nums.empty())
            return 0;
        if (nums.size()==1)
            return nums[0];
        int  count = 1;
        sort(nums.begin(), nums.end());//进行排序，以便之后进行计数叠加
        int std = nums[0];//起初以第一个数为基准
        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] == std)
            {
                count++;
                if (count > nums.size() / 2)
                    return nums[i];
            }
            else
            {
                std = nums[i];//需更换基准数
                count = 1;
            }
        }
        return 0;
    }
};

image.png

效率还是太低，于是我开始想了解大佬们的思路，在此做了一下简单的总结~~~

一、排序

这是我最佩服的了，没有之一

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

“题中说了给定的数组总是存在多数元素。，也就是说肯定有一个元素的个数大于数组长度的一半。我们只需要把这个数组排序，那么数组中间的值肯定是存在最多的元素。”
看看人家，再看看我，啧啧啧，日后还需努力练习，天道酬勤

二、摩尔投票法

public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int val, cnt = 0;
        for (auto x : nums)
        {
            if (!cnt) val = x, cnt ++ ;     //目标值与其他值刚好配对抵消时，重置计数
            else
            {
                if (x == val) cnt ++ ;
                else cnt -- ;
            }
        }
        return val;                         //最后剩下的一定是多于半数的目标值
    }
};

“不同的两数相互抵消，最后剩下的肯定是多于一半的那个数。”

三、哈希数组

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //建立哈希数组找其中出现次数大于n/2的数
        unordered_map<int,int> hash;
        int res=0;
        int len=nums.size();
        for(int i=0;i<len;i++){
            hash[nums[i]]++;
          if(hash[nums[i]]>len/2){
                res=nums[i];
                break;//优化一下
            }    
        }
        return res;
    }
};