剑指offer面试题系列

题目

统计一个数字在排序数组中出现的次数。例如输入排序数组{1，2，3，3，3，4，5}和数字3，由于3在这个数组中出现了 4 次，因此输出4.

思路

如果一个一个遍历然后计数，则算法复杂度为O(n)。并不是最优。

所以，要想降低算法复杂度，则需要考虑O(logn)复杂度存在的可能性。

这时我们可以想到：二分查找。因为它的查找过程算法复杂度恰好为O(logN).

如何将二分查找应用到本题中呢？

比如上面的例子，要搜数字 3.二分的时候，mid变量正好指向 3怎么办？指向小于3的数字怎么办？指向大于3的数字怎么办？

很简单：还是利用二分的道理。

不过需要考虑一个关键的实现问题：就是二分的时候，mid 变量恰好指向该数字第一次出现的位置或者指向数字最后一次出现的位置。

只要找出了这两个位置，即可得出此数字出现的次数。

在下面的代码中 indexFirst 负责前者，indexLast 负责后者。因为要考虑一些细节问题，所以分支判断比较多。

代码

package com.ans;

public class Solution6 {
public static int timesInArray(int num, int[] arr) {
    int times = binarySearch(num, 0, arr.length - 1, arr);
    return times;
}

public static int binarySearch(int number, int start, int end, int[] arr) {
    if (arr == null) {
        System.out.println("输入不合法");
        return -1;
    }
    int times = 0;
    int first = indexFirst(arr, start, end, number);
    int last = indexLast(arr, start, end, number);
    System.out.println("first: " + first);
    System.out.println("last: " + last);
    if (first > -1 && last > -1)
        times = last - first + 1;
    return times;
}

public static int indexFirst(int[] arr, int start, int end, int number) {
    if (start > end)
        return -1;
    int mid = (start + end) / 2;
    int first = 0;
    if (arr[mid] == number) {
        if (mid > 0 && arr[mid - 1] != number || mid == 0)
            first = mid;
        else
            first = indexFirst(arr, start, mid - 1, number);
    }
    else if (arr[mid] < number) {
        first = indexFirst(arr, mid + 1, end, number);
    } else if (arr[mid] > number) {
        first = indexFirst(arr, start, mid - 1, number);
    }

    System.out.println("first value: " + first);

    return first;
}

public static int indexLast(int[] arr, int start, int end, int number) {
    if (start > end)
        return -1;
    int mid = (start + end) / 2;
    int last = end;
    if (arr[mid] == number) {
        if (mid < arr.length - 1 && arr[mid + 1] != number
                || mid == arr.length - 1)
            last = mid;
        else
            last = indexLast(arr, mid + 1, end, number);
    }
    else if (arr[mid] > number) {
        last = indexLast(arr, start, mid - 1, number);
    } else if(arr[mid] < number){
        last = indexLast(arr, mid + 1, end, number);
    }

    System.out.println("last value: " + last);
    return last;
}

public static void main(String[] args) {
    int[] arr = { 2, 2, 2, 2, 2, 2, 3, 3 };
    int count = timesInArray(2, arr);
    System.out.println("出现的次数为：" + count);
}
}

总结

二分查找。