[经典面试题]169. 多数元素

题目描述

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

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

示例 1：

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

示例 2：

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

解题方法分析： 

使用哈希算法（HashMap）来存储每个元素以及出现的次数。通过求解哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数，统计出数组出现的数字次数最多的那一过。

首先循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键，这样就可以通过哈希统计出出现次数最多的数字。

代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 使用map来记录每个数字的出现次数
        std::map<int, int> counts;
        // majority用于记录当前的多数元素，cnt用于记录多数元素出现的次数
        int majority = 0, cnt = 0;
        // 遍历输入数组
        for (int num : nums) {
            // 将当前数字的出现次数加一
            ++counts[num];
            // 如果当前数字的出现次数超过之前记录的多数元素的次数
            if (counts[num] > cnt) {
                // 更新多数元素和出现次数
                majority = num;
                cnt = counts[num];
            }
        }
 
        // 返回最终找到的多数元素
        return majority;
    }
};