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


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

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

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) &#123;
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        &#125;
        int right = i;
        // 若数组中无 target ,则提前返回
        if(j >= 0 && nums[j] != target) return 0;
        // 搜索左边界 right
        i = 0; j = nums.length - 1;
        while(i <= j) &#123;
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        &#125;
        int left = j;
        return right - left - 1;
    &#125;
作者:jyd
链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/

分析

排序数组中的搜索问题,首先想到 二分法 解决。
排序数组 nums 中的所有数字 target 形成一个窗口,记窗口的 左 / 右边界 索引分别为 left 和 right ,
分别对应窗口左边 / 右边的首个元素。

本题要求统计数字 target 的出现次数,可转化为:使用二分法分别找到 左边界
left 和 右边界 right ,易得数字 target 的数量为 right−left−1 。
截屏2021-02-27 下午10.32.47.png
作者:jyd
链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/

优化

image.png

    public int search(int[] nums, int target) &#123;
        return helper(nums, target) - helper(nums, target - 1);
    &#125;
    int helper(int[] nums, int tar) &#123;
        int i = 0, j = nums.length - 1;
        while(i <= j) &#123;
            int m = (i + j) / 2;
            if(nums[m] <= tar) i = m + 1;
            else j = m - 1;
        &#125;
        return i;
    &#125;

作者:jyd
链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
剑指 Offer 36. 二叉搜索树与双向链表 剑指 Offer 36. 二叉搜索树与双向链表
剑指 Offer 36. 二叉搜索树与双向链表输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转
2021-02-27 future
下一篇 
剑指 Offer 39. 数组中出现次数超过一半的数字 剑指 Offer 39. 数组中出现次数超过一半的数字
剑指 Offer 39. 数组中出现次数超过一半的数字class Solution &#123; public int majorityElement(int[] nums) &#123; int x
2021-02-27 future
  目录