给定一个数组，形如 [1, 1, 2 , 3, 3, 3, 3, 4, 6, 6]，给定一个数 n，例如 3，找出给定的数 n 在数组内出现的次数，要求时间复杂度小于 O(n)

[lgwebdream]

No description provided.

[lgwebdream]

扫描下方二维码，获取答案以及详细解析，同时可解锁800+道前端面试题。

[523451928]

var arr = [1, 1, 2, 3, 3, 3, 3, 4, 6, 6]
function getNumCount(arr) {
  const map = {}
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i]
    map[num] = map[num] || {
      indexs: [],
      count: 0
    }
    map[num].indexs.push(i)
    map[num].count++
  }
  return map
}
getNumCount(arr)

[AAA611]

二分查找+左右遍历

简要分析

题目本身实现的功能很简单，但由于要求时间复杂度小于 O(N) 所以不能直接进行遍历数组，那样时间复杂度等于 O(N)
所以题目应该给出的是有序数组，因为如果是无序数组，我们必须要把数组全部遍历一遍才能得出答案，那样的时间复杂度是O(N)
所以，在有序数组的前提下考虑二分查找法，其时间复杂度是对数级别 O（logN）

复杂度

• 时间复杂度：O(logN)
• 空间复杂度：O(1)

const nums = [1, 1, 2, 3, 3, 3, 3, 4, 6, 6]
function fn(nums, target) {
  // 定义左右指针
  let left = 0
  let right = nums.length - 1
  let count = 0
  while (left <= right) {
    // 通过左右指针来算出中间索引
    const mid = Math.floor((right - left) / 2 + left)
    if (nums[mid] === target) {
      // 如果找到目标值，就开始以 mid 索引进行左右遍历查找所有的 target
      let index = mid
      // 先把当前的加上，之后再找左边、右边的
      count++
      index--
      // 找左边的
      while (index >= 0) {
        if (nums[index] === target) {
          count++
          index--
        } else {
          // 遇到不是 target 的值说明左边也不会再有 target 了，直接跳出循环
          break
        }
      }
      // 重新给 index 赋值，来找右边的 target
      index = mid + 1
      // 查找右边的
      while (index < nums.length) {
        if (nums[index] === target) {
          count++
          index++
        } else {
          // 同上，右边也不会有 target 了
          break
        }
      }
      return count
    } else if (nums[mid] < target) {
      // 更新左指针以更新查找的区间
      left = mid + 1
    } else {
      // 更新右指针以更新查找的区间
      right = mid - 1
    }
  }

  // 没找到目标值 target 返回 0
  return count
}
console.log(fn(nums, 1));   // 2
console.log(fn(nums, 2));   // 1
console.log(fn(nums, 3));   // 4
console.log(fn(nums, 4));   // 1
console.log(fn(nums, 6));   // 2