1. Topic Description

Statistics the number of times a number appears in a sorted array.

2. Thoughts on Problem Solving

The title is sorted array, so the idea of "binary search" can be used.

One idea is to find the specified number, and then traverse backwards and forwards, with complexity of O(N).

The other is that you don't need to traverse all the numbers, you just need to find the left and right boundaries of the numbers in the array, and you can get the number of occurrences by making a difference.

3. code

/**
 * Find the left/right boundary of the specified number
 *
 * @param {Array} nums
 * @param {*} target
 * @param {String} mode left | right Look for the left | right boundary
 */
function findBoundary(nums, target, mode) {
  let left = 0,
    right = nums.length - 1;

  while (left < right) {
    let mid = Math.floor((right + left) / 2);

    if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else if (mode === 'left') {
      // nums[mid] === target
      // If the subscript is 0 or the previous element is not equal to target
      // So mid is the left boundary.
      if (mid === 0 || nums[mid - 1] !== target) {
        return mid;
      }
      // Otherwise, continue traversing the left
      right = mid - 1;
    } else if (mode === 'right') {
      // nums[mid] === target
      // If the subscript is the last or last element, it is not equal to target.
      // So mid is the right boundary.
      if (mid === nums.length - 1 || nums[mid + 1] !== target) {
        return mid;
      }
      // Otherwise, continue traversing the right part.
      left = mid + 1;
    }
  }

  // left === right
  if (nums[left] === target) {
    return left;
  }

  return -1;
}

/**
 * Find the number of occurrences of the specified number
 *
 * @param {Array} data
 * @param {*} k
 */
function GetNumberOfK(data, k) {
  const length = data.length;
  if (!length) {
    return 0;
  }

  if (
    findBoundary(data, k, 'right') === -1 &&
    findBoundary(data, k, 'left') === -1
  ) {
    return 0;
  } else {
    return findBoundary(data, k, 'right') - findBoundary(data, k, 'left') + 1;
  }
}

const nums = [1, 2, 3, 3, 3, 4, 5];
console.log(GetNumberOfK(nums, 3));
web Front end development learning Q-q-u-n:  767273102 ，Share learning methods and small details that need attention, and keep updating the latest teaching and learning methods (detailed front-end project teaching video)