数字在升序数组中出现的次数

题目描述

示例

代码

代码1 暴力解法，从左到右遍历一遍

/*
非降序 就是升序
暴力法：从左到右直接遍历一遍
*/
function GetNumberOfK(data, k)
{
    if(data.length === 0) return 0
    
    let count = 0 // 统计出现的次数
    for(let i = 0; i<data.length; i++){
        if(data[i] === k){
            count++
        }
    }
    return count
}

时间复杂度O(n)：最坏情况数据遍历一遍

空间复杂度O(1)

代码2 二分查找，因为是有序的，所以可以使用二分查找，找第一次出现的位置和最后一次出现的位置

/*
使用二分查找
1. 先找自己第一次出现的位置
2. 再找比自己大的位置
3. 最后想减一下 就得到了结果
*/
function GetNumberOfK(data, k)
{
    let left1 = 0, right1 = data.length -1 
    
    // 找第一次出现的位置，left1就是第一次出现的位置
    while(left1 <= right1){
        let mid = Math.floor( (left1 + right1) / 2 )
        
        if(data[mid] < k){ // 中间的这个数 比目标值小，所以left往中间收
            left1 = mid + 1
        } else { // 中间的数比目标值大 right往中间收
            right1 = mid - 1
        }
    }
    // data[mid] < k 判断的是小于，等于的情况也不会进来，所以区间会往小的地方收，为了找第一次出现的位置，所以应该往小的地方收
    // 最后的left 肯定会是第一个出现的索引，如果没有这个值，那left肯定也是理应出现的位置
    // 二分查找，最后区间肯定会收缩到 right比left 小，非常紧凑的一个小区间
    
    
    
    let left2 = 0, right2 = data.length -1 
    // 找目标值最后一次出现的位置 right2 就是最后一次出现的位置
    while(left2 <= right2){
        let mid = Math.floor( ( left2 + right2 ) / 2 )
        
        // 为了找最后一次出现的位置，所以区间应该往大的方向收
        if( data[mid] <= k ){ // 等于的情况，也往右缩，所以整个区间就会往大的方向缩
            left2 = mid + 1
        }else {
            right2 = mid - 1
        }
    }
    // 最后right2的值会比left2的小，结束了循环，此时right2就是目标值最后出现的位置
    // 如果没有目标值，那么，也是这个值理应出现的位置
    
    return right2 - left1 + 1 // 所以用最后一次出现的位置 减去 第一次出现的位置 再加1 就是出现的个数
    /*
    	比如这个样子 [ 1, 2, 3] // 要是找 0 的话， 肯定是没有的
    	所以 left1 最后的值是 0 ，0理应出现在索引0处
    	right2 最后的值是 -1
    	-1 - 0 + 1 = 0 满足结果
    	
    	当 [ 1, 2, 3] 找 2 时，出现了一次
    	left1 = 1
    	right2 = 1
    	1 - 1 + 1 = 1 出现了1次，满足结果
    */
    
}

时间复杂度O(lgN)：假如有n个数，每次查找范围都缩小一半，n/2/2/2... ，假设当除了x次2，找到了结果，即2^x = n，所以 时间复杂度为lgN。

空间复杂度O(1)

题目来源

JZ53 数字在升序数组中出现的次数