1. 题目

统计一个数字在排序数组中出现的次数。

2. 思路解析

题目说是排序数组，所以可以使用“二分查找”的思想。

一种思路是查找到指定数字，然后向前向后遍历，复杂度是 O(N)。

另一种是不需要遍历所有的数字，只需要找到数字在数组中的左右边界即可，做差即可得到出现次数。

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * 寻找指定数字的左 / 右边界
 *
 * @param {Array} nums
 * @param {*} target
 * @param {String} mode left | right 寻找左 | 右边界
 */
function findBoundary(nums, target, mode) {
    let left = 0,
        right = nums.length - 1

    while (left < right) {
        let mid = (right + left) >> 1

        if (nums[mid] > target) {
            right = mid - 1
        } else if (nums[mid] < target) {
            left = mid + 1
        } else if (mode === 'left') {
            // nums[mid] === target
            // 如果下标是0或者前一个元素不等于target
            // 那么mid就是左边界
            if (mid === 0 || nums[mid - 1] !== target) {
                return mid
            }
            // 否则，继续在左部分遍历
            right = mid - 1
        } else if (mode === 'right') {
            // nums[mid] === target
            // 如果下标是最后一位 或者 后一个元素不等于target
            // 那么mid就是右边界
            if (mid === nums.length - 1 || nums[mid + 1] !== target) {
                return mid
            }
            // 否则，继续在右部分遍历
            left = mid + 1
        }
    }

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

    return -1
}

/**
 * 寻找指定数字的出现次数
 *
 * @param {Array} nums
 * @param {*} target
 */
function getTotalTimes(nums, target) {
    const length = nums.length
    if (!length) {
        return 0
    }

    return findBoundary(nums, target, 'right') - findBoundary(nums, target, 'left') + 1
}

/**
 * 以下是测试代码
 */

const nums = [1, 2, 3, 3, 3, 4, 5]
console.log(getTotalTimes(nums, 3))