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

栏目: IT技术 · 发布时间: 4年前

内容简介:注意本题难点排序数组中查找数字,性能最优。

题目信息

  • 时间: 2019-07-04

  • 题目链接: Leetcode

  • tag:二分查找 哈希表

  • 难易程度:简单

  • 题目描述:

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

示例1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例2:

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

注意

1. 0 <= 数组长度 <= 50000

解题思路

本题难点

排序数组中查找数字,性能最优。

具体思路

排序数组中的搜索问题,首先想到 二分法 解决。

排序数组 nums 中的所有数字 target 形成一个窗口,记窗口的 左 / 右边界 索引分别为 left 和 right ,分别对应窗口左边 / 右边的首个元素。

统计数字 target 的出现次数,可转化为:使用二分法分别找到 左边界 left 和 右边界 right ,易得数字 target 的数量为 right−left−1 。

  • 计算中点 m=(i+j)/2(向下取整)
  • 若 nums[m]<target ,则 target 在闭区间 [m+1,j] 中,因此执行 i=m+1;
  • 若 nums[m]>target ,则 target 在闭区间 [i,m−1] 中,因此执行 j=m−1;
  • 若 nums[m]=target ,则右边界 right 在闭区间 [m+1,j] 中;左边界 left 在闭区间 [i,m−1] 中。
    • 若查找 右边界 right ,则执行 i=m+1 ;(跳出时 i指向右边界)
    • 若查找 左边界 left ,则执行 j=m−1 ;(跳出时 j指向左边界)

提示:查找完右边界后,可用 nums[j]=j 判断数组中是否包含 target ,若不包含则直接提前返回 0 ,无需后续查找左边界。查找完右边界后,左边界 left一定在闭区间 [0,j] 中,因此直接从此区间开始二分查找即可。

代码

class Solution {
    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        // 若数组中无 target ,则提前返回
        if(j >= 0 && nums[j] != target) return 0;
        // 搜索左边界 right
        i = 0; 
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }
}

复杂度分析:

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

其他优秀解答

解题思路

直接遍历排序数组,计数。

代码

class Solution {
    public int search(int[] nums, int target) {
        int count = 0;
        for(int num : nums){
            if(num == target){
              count++;
            }
        }
        return count;
    }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

腾讯之道

腾讯之道

艾永亮、刘官华、梁璐 / 机械工业出版社 / 2016-7-19 / 59

放眼整个中国乃至全球,腾讯都是一家成功的互联网企业,它代表中国企业在世界互联网版图中竖起了一面高高的旗帜。腾讯为何能取得如此大的成就,它的成功方法和商业逻辑是什么?你是不是和无数中国企业和商界人士一样,都想向腾讯取取经,但是又不得其门而入? 腾讯一直以低调、务实著称,所 以腾讯及其内部员工都极少对外界分享他们的经验;加之腾讯的商业模式多元、业务繁多且交叉、体量又极其庞大,使得从外部来系统研究......一起来看看 《腾讯之道》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具