每天一道剑指offer-数字在排序数组中出现的次数
每天一道剑指offer-数字在排序数组中出现的次数 https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=11190&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目详述
统计一个数字在排序数组中出现的次数。
题目详解
思路
- 有序和数组这个两个字眼结合起来，肯定是要用到二分查找这一类；
- 首先就是找最左侧的下标，利用二分查找首先是找到有一个值是与目标值target是相等的，然后因为是找最左侧的下标，所以把right=mid-1来一直往左边去逼近最左侧的值；
- 至于找最右侧的下标就是，将left=mid+1,来去逼近最右侧的下标；
- 如果没有找到则说明不存在返回-1；
示例
- 这里举一个例子帮助大家理解，对于数组[1,2,4,4,4,4,4,5,6]，找4的最左下标。
- 对于这个数目来说，lfet,right,mid分别代表下标值首先left=0.right=8,所以mid=(0+8)/2 = 4；
- 由于target=4与nums[mid]相等，所以此时记录下来这个下标，也就是mid的值4，这个下标是可能的最左的4的下标所以要记录保存一下；
- 观察这个数组，可以知道，最左的4的下标是2，所以为了找到这个最左的下标，需要令right的值去等于mid-1;这样就把right这一边慢慢地往左靠，因为是找最左的嘛~，所以肯定是要缩小right的的值去逼近这个最左的4，直到找到这个最左的4为止~；
- 找最右边的4的思路也是一样的哦，就是令left=mid+1去逼近最右边的这个4.
代码
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int leftIndex = -1,start=0,end=array.length-1,rightIndex=-1;
while(start <= end)
{
int mid = (start+end)/2;
if(array[mid] > k)
{
end = mid-1;
}else if(array[mid] < k){
start = mid+1;
}else{
leftIndex = mid;
end = mid-1;
}
}
start = 0;
end = array.length-1;
while(start <= end)
{
int mid = (start+end)/2;
if(array[mid] > k)
{
end = mid-1;
}else if(array[mid] < k){
start = mid+1;
}else{
rightIndex = mid;
start = mid+1;
}
}
if(array.length == 0 || rightIndex == -1)
return 0;
return rightIndex-leftIndex+1;
}
}举报
腾讯云开发者
