37 劍指offer --數字在排序數組中出現的次數

                              數字在排序數組中出現的次數

題目

統計一個數字在排序數組中出現的次數。

思路

既然是已經排序好的數組，那麼第一個想到的就是二分查找法。

做法就是使用二分法找到數字在數組中出現的第一個位置，再利用二分法找到數字在數組中出現的第二個位置。時間複雜度為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);
    }
}