阅读 258

每日一算--求众数

题目

给定一个大小为 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]  
}
复制代码

总结

关注下面的标签,发现更多相似文章
评论