1536. 在排序数组中查找元素的第一个和最后一个位置
2021-05-03 01:27
标签：位置 car markdown arc hint des @param elf starting 给定一个按照升序排列的整数数组 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 样例 1: 样例 2: 二分法 + 两个单指针 时间复杂度:O(log N) 空间复杂度:O(1) 注：lintcode通过，但是测[0,1],1的时候有问题，需要输出[1,1]，后面为调式版本 1536. 在排序数组中查找元素的第一个和最后一个位置 标签：位置 car markdown arc hint des @param elf starting 原文地址：https://www.cnblogs.com/yunxintryyoubest/p/13200392.html1536. 在排序数组中查找元素的第一个和最后一个位置
nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。[-1, -1]。样例
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
class Solution:
"""
@param nums: the array of integers
@param target:
@return: the starting and ending position
"""
def searchRange(self, nums, target):
# Write your code here.
#二分法，首先先定位到等于target的位置，然后target两边走，确定起点和终点
if not nums: return [-1, -1]
#初始化
x, y = -1, -1
length = len(nums)
start, end = 0, length - 1
#二分查找
while start + 1 end:
mid = start + (end - start) // 2
if nums[mid] > target:
end = mid
elif nums[mid] target:
start = mid
else:
#如果两者相等的话，则开始target找起点和终点
left, right = mid, mid
while left >= 0:
if (nums[left] == target):
x = left
else:
break
left -= 1
while right 1:
if (nums[right] == target):
y = right
else:
break
right += 1
break
return [x, y]
class Solution:
"""
@param nums: the array of integers
@param target:
@return: the starting and ending position
"""
def searchRange(self, nums, target):
# Write your code here.
#二分法，首先先定位到等于target的位置，然后target两边走，确定起点和终点
if not nums: return [-1, -1]
#初始化
x, y = -1, -1
length = len(nums)
start, end = 0, length - 1
left, right = 0, length - 1
#二分查找
while start + 1 end:
mid = start + (end - start) // 2
if nums[mid] > target:
end = mid
elif nums[mid] target:
start = mid
else:
left, right = mid, mid
break
if nums[start] == target:
left, right = start, start
elif nums[end] == target:
left, right = end, end
#如果两者相等的话，则开始target找起点和终点
while left >= 0:
if (nums[left] == target):
x = left
else:
break
left -= 1
while right 1:
if (nums[right] == target):
y = right
else:
break
right += 1
return [x, y]
文章标题：1536. 在排序数组中查找元素的第一个和最后一个位置
文章链接：http://soscw.com/index.php/essay/81576.html