34. Find First and Last Position of Element in Sorted Array
in and of Array Find Element First position
2023-09-27 14:25:31 时间
1. 原始题目
给定一个按照升序排列的整数数组 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]
2. 思路
既然是有序数组,可以2分法。如果存在该元素,那么跳出循环后肯定满足nums[mid]==target ! 否则不存在该元素。
找到该元素后,两个指针分别向左,右移,寻找其初始和结尾位置即可。
3. 解题
1 class Solution: 2 def searchRange(self, nums: List[int], target: int) -> List[int]: 3 if not nums:return[-1,-1] 4 low, high = 0,len(nums)-1 5 while(low<=high): # 二分法 6 mid = int((low+high)/2) 7 if nums[mid]==target: 8 break 9 elif nums[mid]<target: 10 low = mid+1 11 else: 12 high=mid-1
13 results = [-1,-1] 14 print(mid) 15 if low<=high and nums[mid]==target: # 这句话判断是否找到了该元素。low<=high是必须的,否则就不存在该元素 16 i,j = mid,mid # 左右指针 17 while(i>=1 and nums[i-1]==target):i-=1 18 while(j<len(nums)-1 and nums[j+1]==target):j+=1 19 results = [i,j] 20 return results 21
相关文章
- What is Owned Entity? When and why to use Owned Entity in Entity Framework Core?
- What's the difference between tilde(~) and caret(^) in package.json?
- Non-matching values for modulus and p*q in RSA encryption
- Update to enable TLS 1.1 and TLS 1.2 as default secure protocols in WinHTTP in Windows
- What is the difference between ManualResetEvent and AutoResetEvent in .NET?
- How to use Regular Expressions (Regex) in Microsoft Excel both in-cell and loops
- What is the difference between 'classic' and 'integrated' pipeline mode in IIS7?
- What is content-type and datatype in an AJAX request?
- The implementation of iterators in C# and its consequences (part 1) Raymond Chen
- CSRF in asp.net mvc and ap.net core
- What's the difference between HEAD^ and HEAD~ in Git?
- jQuery AJAX and HttpHandlers in ASP.NET
- Authentication and Authorization in ASP.NET Web API
- What's the difference between using “let” and “var” to declare a variable in JavaScript?
- Using SQLXML Bulk Load in the .NET Environment
- SpringBoot The valid characters are defined in RFC 7230 and RFC 3986
- Fail Fast and Fail Safe Iterators in Java
- Announcing the Updated NGINX and NGINX Plus Plug‑In for New Relic (Version 2)
- What is the difference between Reactjs and Rxjs?--React is the V (View) in MVC (Model/View/Controller).
- SQL Server-聚焦EXISTS AND IN性能分析(十六)
- Mysql解决 Expression #11 of SELECT list is not in GROUP BY clause and contains nonaggregated column
- pat 1006 Sign In and Sign Out(25 分)
- How to set JAVA environment variables in Linux or CentOS
- Example of how to use both JDK 7 and JDK 8 in one build.--reference
- leetcode 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置(中等)