53-Ⅰ 在排序数组中查找数字 Ⅰ

Lin2J
2021-07-21 / 0 评论 / 163 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

解题思路:

假设有一个大小为 $target$ 的数字要插入数组 $nums$,根据选择排序的思路,我们可以想到这个数组要插入到 target 的右边界的后面,记这个位置为 $right$。

假设有一个大小为 $x = target-1$ 的数字要插入数组 $nums$,根据前面的叙述,$x$ 应该插在数组中 x 的有边界的后面,记这个位置为 $left$。

那么 $left$ 和 $right$ 有什么关系呢?

可以得知,$left$ 和 $right$ 中间夹着的就是 $target$ 元素,$right - left$ 就是 $target$ 出现的次数。

代码:

public int search(int[] nums, int target) {
    return helper(nums, target) - helper(nums, target - 1);
}

/**
 * 找到一个右边界,可以让 target 插入
 */
private int helper(int[] nums, int target) {
    int i = 0, j = nums.length - 1;
    while (i <= j) {
        int mid = (i + j) / 2;
        if (nums[mid] <= target) {
            i = mid + 1;
        } else {
            j = mid - 1;
        }
    }
    return i;
}

复杂度分析

  • 时间复杂度$O(logN)$:二分法为对数级别的复杂度。
  • 空间复杂度$O(1)$:辅助变量占用常数大小的额外空间。