leetcode-34

34 Find First and Last Position of Element in Sorted Array

题目大意


给定一个升序的数组
给定target
寻找第一个和最后一个的位置
即寻找区间
如果没有找到返回-1
要求时间复杂度为O(log(n))

思路

由于求的是区间没办法直接使用二分法
我们可以把问题进行分解
如果 lo == target == hi 那么就是符合条件的我们把[lo,hi]返回
如果target在lo hi之间 就把根据mid进行成左右两块 再次进行判断
如果返回来的数据里面没有-1 就把他俩拼起来 然后返回 如果有-1 就返回最大的那个值
如果 target 不在 lo hi 之间 我们就直接返回[-1,-1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-1,-1]
def search(low,high):
if nums[low] == target == nums[high]:
return [low,high]
if nums[low]<= target <= nums[high]:
mid = (low+high)//2
l,r = search(low,mid),search(mid+1,high)
return max(l,r) if -1 in l+r else [l[0],r[1]]
return [-1,-1]
return search(0,len(nums)-1)

优化

由于使用的是递归进行分解 对于传入很大量的数据一定会爆栈的:
所以需要进行改造一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
self.ls = -1
self.rs = -1
if not nums:
return [-1,-1]
def search(low,high):
if nums[low] == target == nums[high]:
if self.ls == -1 or self.ls > low:
self.ls = low
if high >self.rs:
self.rs = high
elif nums[low]<= target <= nums[high]:
mid = (low+high)//2
search(low,mid),search(mid+1,high)
search(0,len(nums)-1)
return [self.ls,self.rs]

去掉堆栈 使用ls rs 来记录状态
然而 提高了时间复杂度(我也没搞明白为啥会增加时间复杂度)
但是减小了空间复杂度
优化前:

优化后: