数组中出现次数超过一半的数字

题目链接

• 牛客网

题目描述

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围： 0 ≤n≤50000，数组中元素的值 0≤val≤10000 要求：空间复杂度 O(1)，时间复杂度 O(n)

示例：

// 输入：
[1, 2, 3, 2, 2, 2, 5, 4, 2]

// 返回值：
2

刷题思路

方案一：

• 利用Map计数
• 去重数组，减少循环次数。遍历Map获取出现次数超过一半的数字

方案二：

• 数组排序，升降序都行
• 充分利用indexOf、lastIndexOf方法，获取第一次和最后一次出现的角标索引
• 判断出现区间长度是否超过半数，获取结果

方案三：

• 利用选举法，推选出现次数最高的数字
• 遍历数组，判断该数出现是否超过半数

代码实现

/**
 * 数组中出现次数超过一半的数字
 */

/**
 * Map计数
 * @param numbers
 * @returns {number}
 */
function moreThanHalfNumOne(numbers) {
  const resMap = new Map()
  // 计数
  numbers.forEach((item) => {
    if (resMap.has(item)) {
      resMap.set(item, resMap.get(item) + 1)
    }
    else {
      resMap.set(item, 1)
    }
  })

  // 数组去重
  const arr = [...new Set(numbers)]
  // 找出出现一半的数字
  let result = 0
  arr.forEach((item) => {
    if (2 * resMap.get(item) > numbers.length) {
      result = item
    }
  })
  return result
}

/**
 * 借助数组排序
 * @param numbers
 * @returns {*}
 */
function moreThanHalfNumTwo(numbers) {
  // 排序 升序或降序都行
  numbers = numbers.sort()

  const len = numbers.length
  // 注意：数组长度为1
  if (len === 1) {
    return numbers[0]
  }
  for (let i = 0; i < len; i++) {
    const firstIndex = numbers.indexOf(numbers[i])
    const lastIndex = numbers.lastIndexOf(numbers[i])

    if (firstIndex > -1 && lastIndex > -1 && firstIndex !== lastIndex && 2 * (lastIndex - firstIndex + 1) > len) {
      return numbers[i]
    }
  }

  return 0
}

/**
 * 选举出重复最多，再判断是否超过半数
 * @param numbers
 * @returns {number|*}
 */
function moreThanHalfNumThree(numbers) {
  let cond = -1
  let cnt = 0
  // 选举
  for (let i = 0; i < numbers.length; ++i) {
    if (cnt === 0) {
      cond = numbers[i]
      ++cnt
    }
    else {
      if (cond === numbers[i])
        ++cnt
      else --cnt
    }
  }
  cnt = 0

  // 计数
  for (const k of numbers) {
    if (cond === k)
      ++cnt
  }
  if (cnt > numbers.length / 2)
    return cond
  return 0
}

console.log(moreThanHalfNumOne([1, 2, 3, 2, 2, 2, 5, 4, 2]))
console.log(moreThanHalfNumTwo([1, 2, 3, 2, 2, 2, 5, 4, 2]))
console.log(moreThanHalfNumTwo([1, 1]))
console.log(moreThanHalfNumThree([1, 2, 3, 2, 2, 2, 5, 4, 2]))

一些建议

• 理解Map数据结构，熟练使用api