第53题 – 数字在排序数组中出现的次数

作者: 周伟林 分类: 剑指offer 发布时间: 2018-05-23 13:29

牛客链接

题目描述

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

解题思路

  1. 二分查找
  2. 若找到,则左顾右盼

JavaScript实现

function GetNumberOfK(data, k)
{
    let lo = 0, hi = data.length-1, mid;
    let ifFind = false;
    while(lo <= hi){
        mid = Math.floor((lo+hi)/2);
        if(k === data[mid]){
            ifFind = true;
            break;
        }
        k < data[mid] ? hi = mid-1 : lo = mid+1;
    }
    // console.log(ifFind, mid);
    if(!ifFind) return 0;
    let cnt = 1;
    for(let i = mid-1; data[i]===k && i >= 0; --i)    ++cnt;
    for(let i = mid+1; data[i]===k && i < data.length; ++i)    ++cnt;
    return cnt;
}

let arr = [1,2,3,3,3,3,4,5], k = 3;
console.log(GetNumberOfK(arr, k));   // 4

发表评论

电子邮件地址不会被公开。 必填项已用*标注