LeetCode-169. Majority Element

发表于 分类于

问题描述

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
2
Input: nums = [3,2,3]
Output: 3

Constraints:

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

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
 * @Description: 169. Majority Element
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * @description: 方法一：摩尔选举
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = function (nums) {
  let candidate = null
  let count = 0

  for (const num of nums) {
    if (count === 0) {
      candidate = num
    }
    count += (num === candidate) ? 1 : -1
  }
  return candidate
}

/**
 * @description: 方法二：排序
 * @param {number[]} nums
 * @return {number}
 */
const majorityElement = function (nums) {
  nums.sort((a, b) => a-b)
  let index = Math.floor(nums.length / 2)
  return nums[index]
}