题目：
思路：
数组升序——-二分法
与LeetCode 34：在排序数组中查找元素的第一个和最后一个位置相似，
都用了两个变形的二分法找到数组中目标元素出现的左边界索引和右边界索引，
数字k出现的次数即为： 右边界的索引-左边界的索引+1
Java实现：
public class Solution {
public int GetNumberOfK(int [] array , int k) {
if(array.length==0){
return 0;
}
// 升序 ---二分！
int left=findLeft(array,k);
int right=findRight(array,k);
if(left==-1 && right==-1){
return 0; // 数组中不存在k值
}
return right-left+1;
}
int findLeft(int[] array,int k){ // 寻找左边界
int left=0;
int right=array.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(array[mid]<k){
left=mid+1;
}else if(array[mid]>k){
right=mid-1;
}else if(array[mid]==k && (mid==0 || array[mid-1]<k)){ //左边界
return mid;
}else{ // nums[mid]=k但不是左边界,向左继续寻找左边界
right=mid-1;
}
}
return -1; // 数组中不存在k值
}
int findRight(int[] array,int k){ // 寻找右边界
int left=0;
int right=array.length-1;
while(left<=right){
int mid=left+(right-left)/2;
if(array[mid]<k){
left=mid+1;
}else if(array[mid]>k){
right=mid-1;
}else if(array[mid]==k && (mid==array.length-1 || array[mid+1]>k)){ //右边界
return mid;
}else{ // nums[mid]=k 但不是右边界,向右继续寻找右边界
left=mid+1;
}
}
return -1; // 数组中不存在k值
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89298.html
