剑指Offer Java版 面试题53：在排序数组中查找数字

题目一：数字在排序数组中出现的次数。

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

练习地址

https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2

参考答案

public class Solution {
    public int GetNumberOfK(int[] array, int k) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int first = getFirst(array, k, 0, array.length - 1);
        int last = getLast(array, k, 0, array.length - 1);
        if (first > -1 && last > -1) {
            return last - first + 1;
        } else {
            return 0;
        }
    }
    
    private int getFirst(int[] array, int k, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end) / 2;
        if (array[mid] == k) {
            if (mid > 0 && array[mid - 1] != k || mid == 0) {
                return mid;
            } else {
                end = mid - 1;
            }
        } else if (array[mid] > k) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        return getFirst(array, k, start, end);
    }
    
    private int getLast(int[] array, int k, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end) / 2;
        if (array[mid] == k) {
            if (mid < array.length - 1 && array[mid + 1] != k || mid == array.length - 1) {
                return mid;
            } else {
                start = mid + 1;
            }
        } else if (array[mid] > k) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        return getLast(array, k, start, end);
    }
}

复杂度分析

• 时间复杂度：O(logn)。
• 空间复杂度：O(logn)。

题目二：0~n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0 ~ n-1之内。在范围0 ~ n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

参考答案

public int getMissingNumber(int[] numbers) {
    if (numbers == null || numbers.length == 0) {
        return -1;
    }
    int left = 0, right = numbers.length - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (numbers[mid] != mid) {
            if (mid == 0 || numbers[mid - 1] == mid - 1) {
                return mid;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (left == numbers.length) {
        return left;
    }
    // 无效的输入，比如数组不是按要求排序的，
    // 或者有数字不在0~n-1范围之内
    return -1;
}

复杂度分析

• 时间复杂度：O(logn)。
• 空间复杂度：O(1)。

题目三：数组中数值和下标相等的元素。

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{-3, -1, 1, 3, 5}中，数字3和它的下标相等。

参考答案

public int getNumberSameAsIndex(int[] numbers) {
    if (numbers == null || numbers.length == 0) {
        return -1;
    }
    int left = 0, right = numbers.length - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (numbers[mid] == mid) {
            return mid;
        } else if (numbers[mid] > mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

复杂度分析

• 时间复杂度：O(logn)。
• 空间复杂度：O(1)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题