【力扣LeetCode】34 在排序数组中查找元素的第一个和最后一个位置

2024-08-28 22:38

本文主要是介绍【力扣LeetCode】34 在排序数组中查找元素的第一个和最后一个位置,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述(难度中)

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

你的算法时间复杂度必须是 O(log n) 级别。

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

示例 1:

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

示例 2:

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

链接

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

思路

二分查找,改进二分查找
首先找到要查找元素的第一个。普通的二分查找为找到元素就结束,改进的二分查找为,找到该元素,并且满足该元素要么是数组的第一个元素,要么前一个元素比这个元素小,即说明是待查找的第一个元素,这种情况下才终止。否则按照正常二分查找套路进行即可。
查找元素的最后一个,过程相同,不过元素需要满足的条件改为要么是数组的最后一个元素,要么后一个元素比查找到的元素大。
分两次,一次找第一个,一次找最后一个,可略微剪枝。

代码

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int ansStart = -1;int ansEnd = -1;vector<int> ans;int start = 0;int end = nums.size() - 1;int mid = (start + end) / 2;while(start <= end){mid = (start + end) / 2;if(nums[mid] == target){if(mid == 0 || nums[mid-1] < target){ansStart = mid;break;}else{end = mid - 1;}}else if(nums[mid] > target){end = mid - 1;}else{start = mid + 1;}}if(ansStart >= 0){start = ansStart;end = nums.size() - 1;while(start <= end){mid = (start + end) / 2;if(nums[mid] == target){if(mid == nums.size() - 1 || nums[mid+1] > target){ansEnd = mid;break;}else{start = mid + 1;}}else if(nums[mid] > target){end = mid - 1;}else{start = mid + 1;}}}ans.push_back(ansStart);ans.push_back(ansEnd);return ans;}
};

这篇关于【力扣LeetCode】34 在排序数组中查找元素的第一个和最后一个位置的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1116092

相关文章

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

PyCharm如何更改缓存位置

《PyCharm如何更改缓存位置》:本文主要介绍PyCharm如何更改缓存位置的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录PyCharm更改缓存位置1.打开PyCharm的安装编程目录2.将config、sjsystem、plugins和log的路径

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的