描述
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
在线评测地址:[领扣题库官网](https://www.lintcode.com/problem/1536/?utm_source=sc-tianchi
-sz-0514)
样例1 输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]
样例2 输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
解题思路
不用烧脑, 直接两次无脑二分,求left 和 right。
不过需要注意的是
if numsmid = target: start = mid else: end = mid 得到是right, 我第一次以为是left。 感觉如果再碰到,还是有可能写这个bug出来,究竟怎么想会好一点呢?大家有什么方法?
源代码
class Solution: def searchRange(self, nums, target): if not nums: return [-1, -1] left, right = -1, -1 start, end = 0, len(nums) - 1 while start + 1 end: mid = (start + end) // 2 if nums[mid] = target: start = mid else: end = mid if nums[start] == target: right = start if nums[end] == target: right = end start, end = 0, len(nums) - 1 while start + 1 end: mid = (start + end) // 2 if nums[mid] = target: end = mid else: start = mid if nums[end] == target: left = end if nums[start] == target: left = start if left == -1 and right == -1: return [-1, -1] return [left, right]
更多题解参考:九章官网solution
TOP云 (west.cn)1月25日消息,近日,功夫贷宣布获得4000万人民币A轮融资,本轮...
本文介绍了北京慧达天下如何使用运维编排OOS提高发布效率。 公司介绍 公司名称:...
我们知道效能提升 就是要应用系统方法实践和工具 通过它们改进技术、工程能力和...
本文由网易云音乐实时计算平台研发工程师岳猛分享,主要从以下四个部分将为大家...
约束与限制 只有运行中的云服务器云主机才允许用户登录。 Windows操作系统用户名...
作者 | 亮言 来源 | 阿里技术公众号 一 背景 订单状态流转是交易系统的最为核心...
背景 2020年9月16日 Snowflake成功IPO 交易首日市场估值达到704亿美元 募集资金3...
有很多人在听说大数据之后,会开始纠结JAVA与大数据的区别,甚至还在纠结Java和...
hk 域名 哪里注册? .hk域名 在国内是可以注册的,只要提供了.hk 域名注册 服务...
描述 你正在和你的朋友玩 猜数字 (Bulls and Cows)游戏:你写下一个数字让你的朋...