Nmap 数据算法 docker安装 post flash db2 vue架构 当前线程等待5秒 mysql倒序 基于bootstrap的框架 dwf文件怎么转成dwg pythonassert函数 python中的zip python重复执行 windows安装python环境 python基础知识 java抽象方法 java正则匹配数字 javaabstract java连接sql数据库 ie模拟器 mac地址修改器 莫莫小工具 超级煎蛋卷 pushstate 微信python退出程序 vbs表白代码 橄榄山快模 js关闭当前页面 js小数点保留2位 存储过程写法 微信猜拳 js文件上传 电脑待机费电吗 万能低格工具还原u盘 0x000007a 正则表达式替换 qq游戏黑名单 编写软件 软碟通u盘装系统教程
当前位置: 首页 > 学习教程  > 编程语言

Leetcode 在排序数组中查找元素的第一个和最后一个

2021/1/28 22:39:09 文章标签:

在排序数组中查找元素的第一个和最后一个 题目描述: 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -1]。进阶: 你可以设计…

在排序数组中查找元素的第一个和最后一个

题目描述:

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

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

提示:

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9

题目链接

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1,-1};
        // 首先二分查找
        if(nums.length == 0) return result; // 没有元素
        int left = 0;
        int right = nums.length - 1;
        if(right == left && target == nums[left]){ // 只有一个元素
            result[0] = 0;
            result[1] = 0;
            return result;
        } 
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid] < target){
                left = mid+1;
            }else if(nums[mid] > target){
                right = mid-1;
            }
            // 分别向左和向右扩散
            else{
                int l = mid;
                while(l-1 >= 0 && nums[l - 1] == target){
                    l -- ;
                }
                int r = mid;
                while(r + 1 < nums.length && nums[r + 1] == target){
                    r ++ ;
                } 
                result[0] = l;
                result[1] = r;
                break;
            }
        }
        return result;
    }
}

首先二分查找,如果可以找到target等于数组中的某一个下标为mid的值情况下,继续对其分别向左和向右遍历,找出一个相等区间,然后最终返回即可。


本文链接: http://www.dtmao.cc/news_show_650045.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?