数字在排序数组中出现的次数

题目

统计一个数字在排序数组中出现的次数。

思路

既然是已经排序好的数组，那么第一个想到的就是二分查找法。

做法就是使用二分法找到数字在数组中出现的第一个位置，再利用二分法找到数字在数组中出现的第二个位置。时间复杂度为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);
    }
}