跳至主要內容

169. 多数元素


169. 多数元素open in new window

🟢   🔖  数组 哈希表 分治 计数 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]

Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]

Output: 2

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

Follow-up: Could you solve the problem in linear time and in O(1) space?

题目大意

给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在众数。要求线性时间复杂度和 O(1) 空间复杂度。

解题思路

这道题如果用一个哈希表作为计数器,记录每个元素出现的次数,然后寻找出现次数最多的那个元素,时间和空间复杂度都是 O(N)

想要空间复杂度为 O(1) ,可以用栈的思路:遍历数组,如果栈为空,或者当前元素与栈顶元素相同,则入栈;否则将栈顶元素弹出。

由于数组中的众数出现次数大于 n/2 ,所以经过不断地入栈出栈,互相消除,最终栈内留下的肯定是我们要找的众数。证明如下:

  • 当数组内只有两种元素时,由于众数的数量过半,所以不管顺序如何,经过两两对比,不一样的互相消除,最后栈内留下的都是众数;
  • 当数组内有两种以上的元素时,除众数以外的其他元素还会互相对比消除,所以用于消耗众数的元素数量更少,所以栈内留下的元素就是众数。

实际上我们并不需要真的实现一个栈,只需要记录栈顶元素 major (栈内所有元素一定相同,遇到不相同的不会入栈),以及元素的个数 count ,因此只需要两个变量就够了。

复杂度分析

  • 时间复杂度O(n),其中n 表示 nums 的长度,需要遍历数组一遍。
  • 空间复杂度O(1),用了常数个变量存储中间状态。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
	let major;
	let count = 0;
	for (let item of nums) {
		if (count === 0 || item === major) {
			count++;
			major = item;
		} else {
			count--;
		}
	}
	return major;
};

相关题目

题号标题题解标签难度
229多数元素 IIopen in new window数组 哈希表 计数 1+
1150检查一个数是否在数组中占绝大多数 🔒open in new window数组 二分查找
2404出现最频繁的偶数元素open in new window数组 哈希表 计数
2780合法分割的最小下标open in new window数组 哈希表 排序
3065超过阈值的最少操作数 Iopen in new window数组