[劍指offer] 數字在排序數組中出現的次數

本文首發于我的個人部落格： 尾尾部落

題目描述

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

解題思路

正常的思路就是二分查找了，我們用遞歸的方法實作了查找k第一次出現的下标，用循環的方法實作了查找k最後一次出現的下标。

除此之外，還有另一種奇妙的思路，因為data中都是整數，是以我們不用搜尋k的兩個位置，而是直接搜尋k-0.5和k+0.5這兩個數應該插入的位置，然後相減即可。

參考代碼

法一：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int len = array.length;
        if(len == 0)
            return 0;
        int first = getFirst(array, k, 0, len-1);
        int last = getLast(array, k, 0, len-1);
        if(first != -1 && last != -1){
            return last - first + 1;
        }
        return 0;
    }
    // 遞歸
    public int getFirst(int [] array, int k, int start, int end){
        if(start > end){
            return -1;
        }
        int mid = (start + end) >> 1;
        if(array[mid] > k){
            return getFirst(array, k, start, mid - 1);
        }else if(array[mid] < k){
            return getFirst(array, k, mid + 1, end);
        }else if(mid - 1 >= 0 && array[mid-1] == k){
            return getFirst(array, k, start, mid - 1);
        }else
            return mid;
    }
    // 循環
    public int getLast(int [] array, int k, int start, int end){
        int len = array.length;
        int mid = (start + end) >> 1;
        while(start <= mid){
            if(array[mid] > k)
                end = mid - 1;
            else if(array[mid] < k)
                start = mid + 1;
            else if( mid + 1 < len && array[mid+1] == k)
                start = mid + 1;
            else
                return mid;
            mid = (start + end) >> 1;
        }
        return -1;
    }
}
           

法二：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        return biSearch(array, k+0.5) - biSearch(array, k-0.5);
    }
    public int biSearch(int [] array, double k){
        int start  = 0, end = array.length - 1;
        while(start <= end){
            int mid = start + (end - start)/2;
            if(array[mid] > k){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        return start;
    }
}