描述

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：1000≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(logn)

示例

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

// 输入
[1,3,4,5],6
// 输出
0

解题思路

由题意，非降序数组，即升序数组，因此，可以使用二分法

• 先通过二分法找出 k 在数组中的位置
• 再分别向左右查找

代码实现

/**
 * [JZ53-简单] 数字在升序数组中出现的次数
 *
 * @param data int 整型一维数组
 * @param k int 整型
 * @return int 整型
 */
func getNumFromAscArray(data []int, k int) int {
    if 0 == len(data) {
        return 0
    }

    // 二分查找 k 位置
    left, right, mid, isExist := 0, len(data)-1, 0, false
    for left <= right {
        mid = (left + right) / 2
        if data[mid] == k {
            isExist = true
            break
        } else if data[mid] > k {
            right = right - 1
        } else {
            left = left + 1
        }
    }

    if false == isExist {
        return 0
    }

    // // 向左遍历查找
    count, move := 1, mid
    for {
        move--
        if move < 0 || data[move] != k {
            break
        }
        count++
    }

    // 向右遍历查找
    move = mid
    for {
        move++
        if move >= len(data) || data[move] != k {
            break
        }
        count++
    }

    return count
}