[经典面试题]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;}
};