【附JS、Python、C++题解】Leetcode面试150题（12）多数问题

一、题目

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。
多数元素是指在数组中出现次数大于[n/2]的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

二、思路

1. 本题的关键就是用什么方法统计元素出现的次数，由此会引出多种解法。

① 参考前面题目的先排序后处理思路，在这里也可以先进行排序，一个很有用的信息是，我们要找的多数元素，出现次数必须≥n/2，这意味着排序后的中位数一定就是这个多数元素。

② Boyer-Moore 投票算法：这种算法的核心思想是通过“投票”机制来找到多数元素。每个元素都可以看作是一张票，投给当前的候选元素。

• 当遇到相同的元素时，计数器增加，表示支持当前候选元素的票数增加。
• 当遇到不同的元素时，计数器减少，表示反对当前候选元素的票数增加。
• 当计数器为 0 时，说明当前没有候选元素，可以选择当前元素作为新的候选元素。

在这道题中：

• 设置一个计数器 count，初始值为 0。
• 设置一个候选元素 candidate，初始值为 null。

对于数组中的每个元素 num,如果 num 不等于当前候选元素 candidate，将 count 减 1。如果 num 等于当前候选元素 candidate，将 count 加 1。如果 count 为 0，说明当前没有候选元素，将 num 设为候选元素。

③ 可以用哈希表来简化问题（主要是降低时间复杂度）。这里的映射很明显就是数组元素和元素出现次数之间的映射，也就是可以借助哈希表中的键值对匹配来判断出现次数要不要+1.具体见后续的代码。

三、代码

解法一：先排序后处理

① JavaScript：

 function countTimes(nums){let n = nums.length;nums.sort((a,b)=>a-b);return nums[Math.floor(n/2)];
//这里的Math.floor可以确保结果是一个整数，即向下取整。
}

② C++：

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

③ Python：

def majorityElement(nums]):nums.sort()return nums[len(nums) // 2]

解法二：Boyer-Moore投票算法

① JavaScript：

function countTimes(nums){let major = nulllet count = 0for (let num of nums) {if (count === 0) {major = num}if (major === num) {count++} else {count--}}return major
}

② C++：

int countTimes(const std::vector<int>& nums) {int major = 0;int count = 0;for (int num : nums) {if (count == 0) {major = num;}if (major == num) {count++;} else {count--;}}return major;
}

③ Python：

def count_times(nums):major = Nonecount = 0for num in nums:if count == 0:major = numif major == num:count += 1else:count -= 1return major

解法三：哈希表

① JavaScript：

function countTimes (nums) {let hashTable = {};let n = nums.length;// 遍历数组，统计每个元素的出现次数for (let num of nums) {if (hashTable[num] == null) {hashTable[num] = 1;} else {hashTable[num]++;}}// 找到出现次数大于 n/2 的元素for (let num in hashTable) {if (hashTable[num] > Math.floor(n / 2)) {return parseInt(num);}}return null;  // 如果没有多数元素，返回 null
};

② C++：

int countTimes(const std::vector<int>& nums) {unordered_map<int, int> hashtable;int n = nums.size();// 遍历数组，统计每个元素的出现次数for (int num : nums) {hashtable[num]++;}// 找到出现次数大于 n/2 的元素for (const auto& pair : hashtable) {if (pair.second > n / 2) {return pair.first;}}return -1;  // 如果没有多数元素，返回 -1
}

③ Python：

def count_times(nums):# 使用 Counter 统计每个元素的出现次数counter = Counter(nums)n = len(nums)# 找到出现次数大于 n/2 的元素for num, count in counter.items():if count > n / 2:return numreturn None  # 如果没有多数元素，返回 None

四、反思

1. 之前并不了解Boyer-Moore投票算法，从这道题来看该算法很适合用于高性能要求/内存限制高的题目；

2. 一定要抓住题目中的信息，比如这道题中的n/2，想清楚以后可以简化我们的代码（帮助我们确定中位数一定也就是众数，也就是多数元素）。