题目描述
统计一个数字在排序数组中出现的次数
解题思路
(1)遍历一次求出个数 (2)使用二分查找求出第一个和最后一个的下标。如何求第一个数字呢,假如要找的数字和中间的数字相等,则判断其前面一个数字(下标不越界),假如不相等则是第一个数字。同理可求最后一个数字。需要注意的是数组下标越界问题。
代码:
public static int GetNumberOfK(int[] array, int k) {
int number = 0;
if (array != null && array.length > 0) {
int firstK = getFirstK(array, k);
int lastK = getLastK(array, k);
if (firstK > -1 && lastK > -1)
return lastK - firstK + 1;
}
return number;
}
public static int getFirstK(int[] array, int k) {
int start = 0;
int end = array.length - 1;
int middle;
while (start <= end) {
middle = (start + end) / 2;
int middleNum = array[middle];
if (middleNum == k) {
if ((middle > 0 && (array[middle - 1] != k)) || middle == 0) {
return middle;
} else {
end = middle - 1;
}
} else if (middleNum < k) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return -1;
}
public static int getLastK(int[] array, int k) {
int start = 0;
int end = array.length - 1;
int middle;
while (start <= end) {
middle = (start + end) / 2;
int middleNum = array[middle];
if (middleNum == k) {
if ((middle < end && (array[middle + 1] != k)) || middle == end) {
return middle;
} else {
start = middle + 1;
}
} else if (middleNum < k) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return -1;
}