劍指offer-數字在排序數組中出現的次數
標簽:
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);
}
點擊查看更多內容
為 TA 點贊
評論
評論
共同學習,寫下你的評論
評論加載中...
作者其他優質文章
正在加載中
感謝您的支持,我會繼續努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進行掃碼打賞哦