面试题53：数字在排序数组中出现的次数
题目要求：
统计一个数字在排序数组中出现的次数。例如，输入{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。
解题思路：
排序数组，定位某一个数值的位置，很容易想到二分查找。分成两部分：求第一个出现该值的位置start，求最后一个出现该值得位置end，end-start+1即为所求。
二分法比较关键的一个逻辑如下：
mid = left + (right - left + 1) / 2;
if (data[mid] > k)
right = mid-1;
else if(data[mid] < k)
left = mid+1;
else
right = mid;
mid = left + (right - left + 1) / 2;
if (data[mid] > k)
right = mid-1;
else if(data[mid] < k)
left = mid+1;
else
left = mid;
此处要注意求mid时如下两种写法的差别：
（1） mid = left + (right - left) / 2;
（2） mid = left + (right - left + 1) / 2;
如果left，right之前的数字个数为奇数，那两者没差异，比如left=2，right=6，中间有3,4,5，那么(1)(2)求出的mid都是4。如果中间数字的个数是偶数，比如left=2，right=5，中间有3,4,(1)求出的mid都是3，(2)求出的mid都是4，即(1)求出的mid偏左，(2)求出的偏右。极端特殊情况下，比如有个数组data[7,7,7,7,7]，求k=7出现的次数。
使用(1)的迭代过程为
left=0，right=4，mid=2
left=0，right=2，mid=1
left=0，right=1，mid=0 (注意这里)
left=0，right=0，left==right 且 data[left]=k，返回0
使用(2)的迭代过程为
left=0，right=4，mid=2
left=2，right=4，mid=3
left=3，right=4，mid=4(注意这里)
left=4，right=4，left==right 且 data[left]=k，返回4
4-0+1 = 5，即为所求。
另一个在用二分查找时，要注意的点是求mid时的写法：
（a） mid = (left + right) / 2;
（b） mid = left + (right - left) / 2;
推荐用(b)，最好不要出现(a)，当left、right都是比较大的数时，完成同样的功能，(a)可能造成上溢，但(b)不会。
package chapter6;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/15
* Time : 11:24
* Description:数字在排序数组中出现的次数
**/
public class P263_NumberOfK {
//遍历的话时间复杂度为o(n)
//考虑到数组是排序好的，可使用二分法，时间复杂度o(logn)
public static int getNumberOfK(int[] data,int k){
int start = getStartOfK(data,k);
if(start==-1)
return 0;
int end = getEndOfK(data,start,k);
return end-start+1;
}
public static int getStartOfK(int[] data,int k){
if(data[0]>k || data[data.length-1]<k)
return -1;
int left = 0,right = data.length-1,mid;
while (left<=right) {
if(right==left){
if(data[left]==k)
return left;
else
return -1;
}
//当长度为2，mid取左值
mid = left + (right - left) / 2;
if (data[mid] > k)
right = mid-1;
else if(data[mid] < k)
left = mid+1;
else
right = mid;
}
return -1;
}
public static int getEndOfK(int[] data,int start, int k){
int left = start,right = data.length-1,mid;
while (left<=right){
if(left==right){
if(data[left]==k)
return left;
else
return -1;
}
//当长度为2，mid取右值
mid = left + (right - left + 1) / 2;
if (data[mid] > k)
right = mid-1;
else if(data[mid] < k)
left = mid+1;
else
left = mid;
}
return -1;
}
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));
}
}
运行结果
0
4
8
网友评论