每日一算 -- 求众数

题目

给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在众数。

示例

1
2
输入: [3,2,3]
输出: 3

示例

1
2
输入: [2,2,1,1,1,2,2]
输出: 2

日常找规律

瞬间想到的解法可能就是:

  • 利用对象进行存储出现的次数,很棒
  • 不太容易想到的就是摩尔投票法跟前后PK

实现方式

hashMap实现

  • 时间复杂度 O(n)
  • 空间复杂度 O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    function majorityElement(arr) {
    const hash = {}
    const half = Math.ceil(arr.length / 2)
    for (let i = 0; i < arr.length; i++) {
    if (!hash[arr[i]]) {
    hash[arr[i]] = 0
    }
    hash[arr[i]]++
    if ( hash[arr[i]] >= half) {
    return arr[i]
    }
    }
    }

摩尔投票法

时间复杂度 O(n)
空间复杂度 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function majorityElement(arr) {
let count = 0
let majority = 0
for (let i = 0; i < arr.length; i++) {
if ( count === 0 ) {
count++
majority = arr[i]
} else if (majority == arr[i]){
count++
} else {
count--
}
}
return majority
}

前后PK法

  • 原理,取数组前后的一个数进行PK,只要不相等就删除,这样一对一PK后,剩余的的那个数就一定是众数
  • 时间复杂度 O(n/2)
  • 空间复杂度 O(1)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    function majorityElement(arr) {
    let i = 0
    let j = arr.length - 1
    let count = 0
    for (;i < j;) {
    if ( arr[i] === arr[j]) {
    i++
    count++
    } else {
    if (count > 0) {
    i++
    count--
    } else {
    i++
    j--
    }
    }
    }
    return arr[i]
    }

总结