majority-element.md

169. Majority Element - 多数元素

Tags - 题目标签

Description - 题目描述

EN:

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 * 104
• -109 <= nums[i] <= 109

 

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

ZH-CN:

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

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

 

示例 1：

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

示例 2：

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

 

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

 

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
typescript	64 ms	43.4 MB	2023/03/04 23:05

function majorityElement(nums: number[]): number {
  // candidate vote
  if (nums.length === 1) {
    return nums[0];
  }

  let candidate = undefined, count = 0;

  for (let i = 0; i < nums.length; i++) {
    if (count === 0) {
      candidate = nums[i];
    }
    count += (candidate === nums[i]) ? 1 : -1;
  }

  return candidate;
};

My Notes - 我的笔记

与剑指 offer 某题相同，投票记数法：维护一个 candidate，当当前元素与 candidate 不同，则 count - 1，当 count 为0时，把当前元素赋给candidate。

function majorityElement(nums: number[]): number {
  // candidate vote
  if (nums.length === 1) {
    return nums[0];
  }

  let candidate = undefined, count = 0;

  for (let i = 0; i < nums.length; i++) {
    if (count === 0) {
      candidate = nums[i];
    }
    count += (candidate === nums[i]) ? 1 : -1;
  }

  return candidate;
};