题目
统计一个数字在排序数组中出现的次数。
思路
既然是已经排序好的数组，那么第一个想到的就是二分查找法。
做法就是使用二分法找到数字在数组中出现的第一个位置，再利用二分法找到数字在数组中出现的第二个位置。
时间复杂度为O(logn + logn)，最终的时间复杂度为O(logn)。
举个例子，找到数字k在数组data中出现的次数。
数组data中，数字k出现的第一个位置：我们对数组data进行二分，
如果数组中间的数字小于k，说明k应该出现在中间位置的右边；
如果数组中间的数字大于k，说明k应该出现在中间位置的左边；
如果数组中间的数字等于k，并且中间位置的前一个数字不等于k，说明这个中间数字就是数字k出现的第一个位置。
同理，数字k出现的最后一个位置，也是这样找的。但是判断少有不同。我们使用两个函数分别获得他们。
public class Solution {
/** * 博客上的解题思路，也就是剑指offer的思路 * 首先用递归二分法找到第一个k和最后一个k，然后得到个数 * @param array * @param k * @return */
public int GetNumberOfK(int [] array , int k) {
int num = 0;
if (array != null && array.length >0) {
int firstk = getFirstK(array, k,0, array.length-1);
int lastk = getLastK(array, k,0, array.length-1);
if (firstk > -1 && lastk > -1)
num = lastk -firstk +1;
}
return num;
}
/* * 找到第一个出现的数字的下标 */
public int getFirstK(int [] array, int k,int start, int end) {
if(start > end)
return -1;
int midindex = (start + end)/2;
int middata = array[midindex];
if (middata == k) {
//判断是不是第一个K，前一个不等于K，就是第一个K
if(midindex > 0 && array[midindex - 1]!=k||midindex == 0)
return midindex;
else
end = midindex -1;//如果不是第一个k，那么肯定是在前面找，所以end要往前放
}
else if (middata > k) {
end = midindex -1; //二分，如果这个大于k，所以要在前面找
}
else
start = midindex + 1;// 如果小于k，说明要往后找
return getFirstK(array,k, start, end);
}
/* * 找到最后一个出现的数字的下标 */
public int getLastK(int [] array, int k,int start, int end) {
if(start > end)
return -1;
int midindex = (start + end)/2;
int middata = array[midindex];
if(middata == k) {
//判断是不是最后一个K，后一个不等于K，就是最后一个K
if(midindex < array.length-1 && array[midindex + 1]!= k||midindex ==array.length -1)
return midindex;
else
start = midindex + 1;
}
else if (middata > k) {
end = midindex - 1;
}
else
start = midindex +1;
return getLastK(array, k,start, end);
}
}
leetCode中解法
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] relist = new int[2];
// if(nums.length <=0 ||nums == null){
// return relist;
// }
//求第一个
relist[0] = GetFirst(nums,nums.length,target,0,nums.length-1);
relist[1] = GetLast(nums,nums.length,target,0,nums.length-1);
//求最后一个
return relist;
}
private static int GetFirst(int[] nums, int length, int target, int start, int end) {
if(start > end){
return -1;
}
int middle = (start+end)/2;
if(nums[middle] > target){
//说明开始值在左边
end = middle-1;
}else if(nums[middle] < target){
//说明开始值在右边
start = middle+1;
}else {
//说明开始值可能就在中间
if((middle > 0 && nums[middle-1] != target) || middle ==0){
return middle;
}else {
end = middle-1;
}
}
return GetFirst(nums,length,target,start,end);
}
private static int GetLast(int[] nums, int length, int target, int start, int end) {
if(start > end){
return -1;
}
int middle = (start+end)/2;
if(nums[middle] < target){
//说明结束值在右边
start = middle+1;
}else if(nums[middle] > target){
//说明结束值在左边
end = middle-1;
}else {
//说明开始值可能就在中间
if((middle < length-1 && nums[middle+1] != target)|| middle ==length-1){
return middle;
}else {
start = middle+1;
}
}
return GetLast(nums,length,target,start,end);
}
}
优质文章推荐
1.计算机网络----三次握手四次挥手
2.一篇让你彻底了解http请求报文和响应报文的结构
3.梦想成真-----项目自我介绍
4.一篇让你彻底了解HTTP 的前世今生
5.一篇让你彻底搞定HTTP方法与状态码
6.你们要的设计模式来了
7.震惊！来看《这份程序员面试手册》！！！
8.一字一句教你面试“个人简介”
9.接近30场面试分享
京公网安备 11010502036488号