剑指offer | 39. 数组中出现次数超过一半的数字

布满荆棘的人生 2023-01-01 03:44 78阅读 0赞

**题目**

> 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
> 
> 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

**示例 1:**

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
    输出: 2

**限制：**

1 <= 数组长度 <= 50000

--------------------

**方法一：排序**

*  把数组从小到大（或者从大到小）排序，然后直接输出中间哪个数必定是要找的数，因为数字如果出现的次数要超过数组长度的一半，那么，排序之后最中间的那个数必定是我们要找的。

class Solution { 
    public:
        int majorityElement(vector<int>& nums) { 
            sort(nums.begin(),nums.end());
            int l=0;
            int r=nums.size()-1;
            int mid=(l+r)/2;
            return nums[mid];
        }
    };

**方法二： hashmap**

*  hashmap存储数组中值出现的次数

class Solution { 
    public:
        int majorityElement(vector<int>& nums) { 
            unordered_map<int, int> match;
            int len = nums.size(), res = 10086;
            if(len == 1 || len == 2){ 
                return nums[0];
            }
    
            for(int i = 0; i < len; ++i){ 
                match[nums[i]] ++;
                if(match[nums[i]] > (len / 2)){ 
                    res = nums[i];
                    break;
                }
            }
            return res;
        }
    };

**方法三：摩尔投票法**

*  先让 res = nums\[0\]，mole\_vote = 1，然后往后迭代。但凡遇到下一个不等于 res，就让 mole\_vote --（相当于和一个敌人同归于尽）；如果下一个等于 res，则mole\_vote ++。如果 mole\_vote == 0 了，就让 res 等于当前 numes\[i\]。

class Solution { 
    public:
        int majorityElement(vector<int>& nums) { 
            int moleVote = 0, res = 0;
            for(int i : nums){ 
                if(moleVote == 0){ 
                    res = i;
                }
                moleVote += res == i ? 1 : -1;
            }
            return res;
        }
    };

参考：[字节题库 - \#剑39 - 简单 - 数组中出现次数超过一半的数字 - 1刷][- _39 - _ - _ - 1]

[- _39 - _ - _ - 1]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/zi-jie-ti-ku-jian-39-jian-dan-shu-zu-zhong-chu-xia/