劍指offer-數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
標(biāo)簽:
JavaScript
统计一个数字在排序数组中出现的次数。既然是有序数组,采用二分查找的思路,先找到目标值所在位置,然后遍历目标值左右的数字,统计目标值出现的次数。
function GetNumberOfK(data, k)
{
// write code here
if(data.length==0) return 0;
//由于数组是有序的 所以利用二分查找
var left=0;
var right=data.length-1;
var count=0;
var mid;
while(left<=right){
mid=Math.floor((left+right)/2);
if(k>=data[mid]){
left=mid+1;
}
else{
right=mid-1;
}
}
var index=mid;
//从中间值右侧判断后面的数是否与目标值相等
for(var i=index;data[i]==k;i++){
count++;
}
//从中间值左侧怕短后面的数是否与目标值相等
for(var j=index-1;data[j]==k;j--){
count++;
}
console.log(count);
}
點擊查看更多內(nèi)容
為 TA 點贊
評論
評論
共同學(xué)習(xí),寫下你的評論
評論加載中...
作者其他優(yōu)質(zhì)文章
正在加載中
感謝您的支持,我會繼續(xù)努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進(jìn)行掃碼打賞哦