【Offer】[53-1] 【数字在排序数组中出现的次数】

• 题目描述
• 思路分析
• 测试用例
• Java代码
• 代码链接

题目描述

统计一个数字在排序数组中出现的次数。例如，输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。

牛客网刷题地址

思路分析

利用二分查找法查找到第一个k和最后一个k出现的位置，就可以统计出k出现的次数，比较k与中间值mid的大小：

1. 如果k小于mid，则第一个k出现在前半部分，
2. 如果k大于mid，则第一个k出现在后半部分，
3. 如果相等，这是判断中间值是否是第一个k，如果中间值前面的值还是k，则第一个k出现在前半部分。

测试用例

1. 功能测试：数组中包含要查找的数字;数组中没有要查找的数字;要查找的数字在数组中出现一次/多次。
2. 边界值测试：查找数组中的最大值、最小值;数组中只有一个数字。
3. 特殊输入测试：表示数组的指针为nullptr指针。

Java代码

public class Offer053_01 {
public static void main(String[] args) {
test1();
test2();
test3(); } public static int GetNumberOfK(int[] array, int k) {
return Solution1(array, k);
} private static int Solution1(int[] array, int k) {
if (array == null || array.length <= 0) {
return 0;
}
int firstK = getFirstK(array, 0, array.length - 1, k);
if (firstK == -1) {
return 0;
}
int lastK = getLastK(array, 0, array.length - 1, k); return lastK - firstK + 1; } private static int getFirstK(int[] array,int start,int end,int k) {
if(start>end) {
return -1;
}
int mid = (start+end)>>1;
if(array[mid]==k) {
if(mid==0 || array[mid-1]!=k) {
return mid;
}else {
end = mid-1;
}
}else if(array[mid]<k) {
start = mid+1;
}else {
end = mid-1;
}
return getFirstK(array, start, end, k);
} private static int getLastK(int[] array,int start,int end,int k) {
if(start>end) {
return -1;
}
int mid = (start+end)>>1;
if(array[mid]==k) {
if(mid==array.length-1 || array[mid+1]!=k) {
return mid;
}else {
start = mid+1;
} }else if(array[mid]<k) {
start = mid+1;
}else {
end = mid-1;
}
return getLastK(array, start, end, k);
} private static void test1() { } private static void test2() { } private static void test3() { }}


代码链接

剑指Offer代码-Java