每日一算--求众数

题目

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

示例

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

示例

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

日常找规律

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

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

实现方式

hashMap实现

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

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)

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)

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]  
}

总结

• 求众数
• leetcode.com/problems/ma…