剑指offer53~在排序数组中查找数字
程序员文章站
2023-12-28 11:56:34
...
The Amount Of A Certain Character In Sorted Array
Description
统计一个数字在排序数组中出现的次数。例如,输入排序数组{1,2,3,3,3,3,4,5}和数字3,由于3在这个数组中出现了4次,因此输出4.
Solution
- 方法一:暴力搜索
在O(n)的时间内便利,统计这个数字出现的次数。
- 方法二:二分法定位数字出现的位置,按照大小关系,调整两个指针的位置,利用递归循环调用自己来不断进行修正,直至搜索出。
Code
public class pointtooffer53 {
public static int GetNumberOfk(int[]data , int k) {
if(data==null||data.length==0)
return -1;
return min(data, k,0,data.length-1);
}
public static int min(int []data,int k,int left,int right ){
if(left>right)
return 0;
int mid=left+(right-left)/2;
if(data[mid]>k)
return min(data,k,left,mid-1);
else if(data[mid]<k)
return min(data,k,mid+1,right);
else return 1+min(data,k,left,mid-1)+min(data,k,mid+1,right);
//return 0;
}
public static void main(String[] args){
int[] data1 = new int[]{1,2,3,3,3,3,5,6};
int[] data2 = new int[]{1,2,3,3,3,3,4,5};
int[] data3 = new int[]{3,3,3,3,3,3,3,3};
System.out.println(GetNumberOfk(data1,4));
System.out.println(GetNumberOfk(data2,3));
System.out.println(GetNumberOfk(data3,3));
}
}
Appendix
1.和上一道11题目差不多,出不多的思路。双指针,二分法;
2.注意mid-1赋给right,mid+1赋给left,不然下标会越界;
3.计算公式就是两个1+小于号的+大于号的
4.递归简单应用