题目来源:
https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=11190&tPage=2&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking
题目描述:
统计一个数字在排序数组中出现的次数。
代码如下:
public class Solution {
public int GetNumberOfK(int[] array, int k) {
if (array.length == 0) {
return 0;
}
int firstIndex = getFirstIndex(array, k);
int lastIndex = getLastIndex(array, k);
return lastIndex - firstIndex + 1;
}
private int getFirstIndex(int[] array, int k) {
int start = 0, end = array.length - 1;
int mid = (start + end) / 2;
while (start <= end) {
if (array[mid] < k) {
start = mid + 1;
} else {
end = mid - 1;
}
mid = (start + end) / 2;
}
return start;
}
private int getLastIndex(int[] array, int k) {
int start = 0, end = array.length - 1;
int mid = (start + end) / 2;
while (start <= end) {
if (array[mid] <= k) {
start = mid + 1;
} else {
end = mid - 1;
}
mid = (start + end) / 2;
}
return end;
}
}