《剑指offer第二版》面试题53：在排序数组中查找数组（jav

题目描述

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

解题思路

1. 可利用二分查找的方式，分别找出第一个出现的数字K，和最后出现的数字K，然后这两个位置的下标相减即可。
2. 若当数组中间的数字M大于K,则第一个K肯定在数组左边。如果M小于K,则第一个K肯定在右边。如果M等于K，若M前一个数字不为K，则M就是第一个K。如果M前一个数字仍然等于K，则第一个K还是在左边。如此反复即可求得第一个K的位置。
3. 同理可求得最后一个K的位置。

代码

int getNumberOfK(int[] arr, int k){
    // 求第一个K
    int first = findFirstKIndex(arr, k);
    // 求最后一个K
    int last = findLastKIndex(arr, k);
    if (first > -1 && last > -1) {
        return last - first + 1;
    }
    return -1;
}

int findFirstKIndex(int[] arr, int k) {
    if (arr == null || arr.length <=0) {
        return -1;
    }
    int start = 0;
    int end  = arr.length - 1;
    while (start <= end) {
        int middleIndex = start + (end - start) / 2;
        if (arr[middleIndex] > k) {
            end = middleIndex - 1;
        } else if (arr[middleIndex] < k) {
            start = middleIndex + 1;
        } else {
            if(middleIndex == 0 || ((middleIndex - 1) >= 0 && arr[middleIndex - 1] != k )) {
                // 若前数字不等k，则当前位置就是第一个k
                return middleIndex;
            } else {
                end = middleIndex - 1;
            }
        }
     }
    return -1;
}
int findLastKIndex(int[] arr, int k) {
    if (arr == null || arr.length <=0) {
        return -1;
    }

    int start = 0;
    int end  = arr.length - 1;
    while (start <= end) {
        int middleIndex = start + (end - start) / 2;
        if (arr[middleIndex] > k) {
            end = middleIndex - 1;
        } else if (arr[middleIndex] < k) {
            start = middleIndex + 1;
        } else {
            if(middleIndex == arr.length - 1 || ((middleIndex + 1) < arr.length && arr[middleIndex + 1] != k )) {
                // 若后一个数字不等k，则当前位置就是最后一个k
                return middleIndex;
            } else {
                start = middleIndex + 1;
            }
        }
    }
    return -1;
}

题目二

• 题目描述：0 ~ n-1中缺失的数字。一个长度为n-1的递增数组中所有数字都是唯一的，并且每个数的都在0 ~ n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在改数组中，请找出该数字。
• 解题思路：
  1. 因为数组是排序的，因此在这个缺失的数字之前，数组的下标和对应的值是相同的。
  2. 在这个缺失的数字之后，数组的下标比数组的值大。
  3. 因此可以用二分查找法，找出第一个下标和值不相同的位置。该位置即为缺失的数字。