Leetcode 34. Find First and Last Position of Element in Sorted Array

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Find First and Last Position of Element in Sorted Array

2. Solution

解析:最容易想到的就是二分查找,只是要进行一些修改,另一个方法是分别从前往后找以及从后往前找,满足条件就退出。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
def searchRange(self, nums, target):
length = len(nums)
start = -1
end = -1
left = 0
right = length - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
if mid == 0 or nums[mid - 1] < target:
start = mid
break
right = mid - 1
left = 0
right = length - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
if mid == length - 1 or nums[mid + 1] > target:
end = mid
break
left = mid + 1
return [start, end]
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def searchRange(self, nums, target):
length = len(nums)
start = -1
end = -1
for i in range(length):
if nums[i] == target:
start = i
break
if nums[i] > target:
break
if start == -1:
return [start, end]
for i in range(length -1 , -1, -1):
if nums[i] == target:
end = i
break
if nums[i] < target:
break
return [start, end]

Reference

  1. https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
如果有收获,可以请我喝杯咖啡!