题解 | #数字在升序数组中出现的次数#
数字在升序数组中出现的次数
http://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2
1、二分法 空间复杂度O(1),时间复杂度O(logn)
思路：二分法找目标值的begin和end，最后begin-end+1，重点是如何找begin和end
1、找begin
while(left<right){ mid = (left+right)>>1; //如果中点值>=目标值，那么证明目标值在(left，min]的左开又闭区间内,那么mid很有可能也是begin //所以mid也得取到 if(array[mid]>=k){ right = mid; } //如果中点值<目标值,那么证明目标值在（min，right）的开区间内，那left=mid+1即可 else{ left = mid+1; } }2、找end
while(left<right){ mid = (left+right+1)>>1; //如果中点值<=目标值，那么证明目标值在[mid，right)的左闭又开区间内,那么mid很有可能也是end //所以mid也得取到 if(array[mid]<=k) { right = mid; } //如果中点值>目标值,那么证明目标值在（left，mid）的开区间内，那right=mid-1即可 else{ right = mid-1; } }可以好好理解上面两个模版公式，其中如果出现mid-1，那么在 mid的取值要记得（left+right+1）/2，要加上1，因为要避免向下取整
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array.length==0){
return 0;
}
int left = 0;
int right = array.length-1;
int mid;
//找左边界
while(left<right){
mid = (left+right)>>1;
if(array[mid]>=k){
right = mid;
}
else{
left = mid+1;
}
}
//如果目标值都没有，直接返回0
if (array[right]!=k){
return 0;
}
int l = right;
left = 0;
right = array.length-1;
//找右边界
while(left<right){
mid = (left+right+1)>>1;
if(array[mid]<=k){
left = mid;
}
else{
right= mid-1;
}
}
int r = right;
return r-l+1;
}
}
投递美团等公司10个岗位
国家电网工作强度 101人发布