专栏首页YuanXin【剑指offer:在排序数组中查找数字】搜索左右边界:从两边向中间、二分查找

【剑指offer:在排序数组中查找数字】搜索左右边界:从两边向中间、二分查找

题目描述:统计一个数字在排序数组中出现的次数。

这题要解决的核心问题就是:搜索数字出现的左右边界。边界的差值,就是出现次数。

解法 1: 从两边向中间

思路比较简单:

  • 从数组左侧向右遍历,遇到目标数字 target,停止,记录下标 left
  • 从数组右侧向左遍历,遇到目标数字 target,停止,记录下标 right
  • 如果 right 小于 left,那么说明没出现,返回 0;否则返回 right - left + 1

代码实现:

// ac地址:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2020-03-13-find-num-in-sorted/
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    if (!nums.length) return 0;

    let left = 0,
        right = nums.length - 1;
    while (nums[left] !== target && left < nums.length) {
        ++left;
    }
    while (nums[right] !== target && right >= 0) {
        --right;
    }

    return left <= right ? right - left + 1 : 0;
};

时间复杂度是$O(N)$,空间复杂度是$O(1)$。

解法 2: 二分查找(巧妙)

二分查找一般用来查找数字在有序数组中是否出现过。进一步想,它可以用来不断在子序列中搜索对应数字。所以,我们就可以用它来向左边子序列中不断搜索,确认左边界;同样的思路,确认右边界。

这可能还是有点抽象,举个 ?。以数组 2、3、3、3、2 为例,我们要搜索数字 3 的左右边界。假设我们先尝试搜索左边界下标 start。

按照二分法思路,arr[mid] = arr[2] = 3,更新 start 为 2,同时缩小搜索范围到 [0, mid - 1] = [0, 1]。继续按照二分思路,搜索范围缩小到[1, 1],发现值为 3,更新 start 为 1。结束。

按同样方法,可以获得右边界下标 end。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2020-03-13-find-num-in-sorted/
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    const length = nums.length;
    let start = -1,
        end = -1;

    let left = 0,
        right = length - 1;
    // 找到左边界:找到第一次出现
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            start = mid;
            right = mid - 1; // important
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    left = 0;
    right = length - 1;
    // 找到右边界:找到第2次出现
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            end = mid;
            left = mid + 1; // important
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return start <= end && start !== -1 ? end - start + 1 : 0;
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指offer:和为s的两个数字】双指针

    题目描述:输入一个递增排序的数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。如果有多对数字的和等于 s,则输出任意一对即可。

    心谭博客
  • 【剑指offer:0~n-1中缺失的数字】二分查找的妙用

    题目描述:一个长度为 n-1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 ~ n-1 之内。在范围 0 ~ n-1 内的 n 个数字中有且只...

    心谭博客
  • LeetCode 53.最大子序列和 - JavaScript

    题目描述:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    心谭博客
  • [Leetcode][python]Find First and Last Position of Element in Sorted Array/在排序数组中查找元素的第一个和最后一个位置

    给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

    后端技术漫谈
  • 二分查找两种实现,附详细注释

    链接:https://leetcode-cn.com/problems/binary-search

    double
  • Binary Search - 33. Search in Rotated Sorted Array

    Suppose an array sorted in ascending order is rotated at some pivot unknown to y...

    用户5705150
  • OMG,我从来没想过,二分查找还有诗?!

    二分查找是极其简单容易理解的一种算法,但它的变形与细节也是极其繁杂的,一不小心就容易踩坑。

    五分钟学算法
  • 二分查找算法细节详解

    我相信对很多读者朋友来说,编写二分查找的算法代码属于玄学编程,虽然看起来很简单,就是会出错,要么会漏个等号,要么少加个 1。

    haifeiWu
  • 基于二分搜索法的floor与ceil

    此时使用上述二分查找算法,搜索出来的index为3。那如果我想要获取最左侧等于target的index或最右侧等于target的index呢?此时上述算法失效!

    公众号guangcity
  • LeetCode<二分搜索> 33 & 81 Search in Rotated Sorted Array I&II

    Suppose an array sorted in ascending order is rotated at some pivot unknown to y...

    大学里的混子

扫码关注云+社区

领取腾讯云代金券