題目53：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

舉例說(shuō)明

例如輸入排序數(shù)組｛ 1, 2, 3, 3, 3, 3, 4, 5｝和數(shù)字 3，由于 3 在這個(gè)數(shù)組中出現(xiàn)了 4 次，因此輸出 4 。

思路

利用改進(jìn)的二分算法。

• 如何用二分查找算法在數(shù)組中找到第一個(gè) k，二分查找算法總是先拿數(shù)組中間的數(shù)字和 k 作比較。

1. 如果中間的數(shù)字比 k 大，那么 k 只有可能出現(xiàn)在數(shù)組的前半段，下一輪我們只在數(shù)組的前半段查找就可以了。

2. 如果中間的數(shù)字比 k 小，那么 k 只有可能出現(xiàn)在數(shù)組的后半段，下一輪我們只在數(shù)組的后半段查找就可以了。

3. 如果中間的數(shù)字和 k 相等呢？
   3.1 我們先判斷這個(gè)數(shù)字是不是第一個(gè) k。如果位于中間數(shù)字的前面一個(gè)數(shù)字不是 k,此時(shí)中間的數(shù)字剛好就是第一個(gè) k。
   3.2 如果中間數(shù)字的前面一個(gè)數(shù)字也是 k，也就是說(shuō)第一個(gè) k 肯定在數(shù)組的前半段， 下一輪我們?nèi)匀恍枰跀?shù)組的前半段查找。

• 同樣的思路在排序數(shù)組中找到最后一個(gè) k。

1. 如果中間數(shù)字比 k 大，那么 k 只能出現(xiàn)在數(shù)組的前半段。
2. 如果中間數(shù)字比 k 小，k 就只能出現(xiàn)在數(shù)組的后半段。
3. 如果中間數(shù)字等于 k 呢？
   3.1 我們需要判斷這個(gè) k 是不是最后一個(gè) k，也就是中間數(shù)字的下一個(gè)數(shù)字是不是也等于 k。
   3.2 如果下一個(gè)數(shù)字不是 k，則中間數(shù)字就是最后一個(gè) k 了，否則下一輪我們還是要在數(shù)組的后半段中去查找。

代碼實(shí)現(xiàn)

public class _5300{
    private static int getFirstK(int[] data, int k, int start, int end) {
        if (data == null || data.length < 1 || start > end) {
            return -1;
        }
        int midIdx = start + (end - start) / 2;
        int midData = data[midIdx];
        if (midData == k) {
            if (midIdx > 0 && data[midIdx - 1] != k || midIdx == 0) {
                return midIdx;
            } else {
                end = midIdx - 1;
            }
        } else if (midData > k) {
            end = midIdx - 1;
        } else {
            start = midIdx + 1;
        }
        return getFirstK(data, k, start, end);
    }
 
    private static int getLastK(int[] data, int k, int start, int end) {
        if (data == null || data.length < 1 || start > end) {
            return -1;
        }
        int midIdx = start + (end - start) / 2;
        int midData = data[midIdx];
        if (midData == k) {
            if (midIdx + 1 < data.length && data[midIdx + 1] != k || midIdx == data.length - 1) {
                return midIdx;
            } else {
                start = midIdx + 1;
            }
        } else if (midData < k) {
            start = midIdx + 1;
        } else {
            end = midIdx - 1;
        }
        return getLastK(data, k, start, end);
    }
 
    public static int getNumberOfK(int[] data, int k) {
        int number = 0;
        if (data != null && data.length > 0) {
            int first = getFirstK(data, k, 0, data.length - 1);
            int last = getLastK(data, k, 0, data.length - 1);
            if (first > -1 && last > -1) {
                number = last - first + 1;
            }
        }
        return number;
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 3, 3, 3, 4, 5};
        System.out.println(getNumberOfK(data, 3)); // 4
    }
}

輸出

4