题目描述

[EN | CN]

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 $O(\log n)$ 级别。

如果数组中不存在目标值,返回 [-1, -1]

示例 1:

1
2
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

1
2
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解法 1:先找 target 再往两边扩展

既然题目要求复杂度为 $O(\log n)$,那么我们可以先找到 target 然后再往两边拓展。这个思路比较直接,也比较容易实现,但其实不是严格的 $O(\log n)$ 的方法。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(\log n)$,最坏情况下达到 $O(n)$。
  • 空间复杂度为 $O(1)$,不需要额外空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] < target:
                l = m + 1
            elif nums[m] > target:
                r = m - 1
            else:
                l, r = m, m
                while l > 0 and nums[l - 1] == target:
                    l -= 1
                while r < len(nums) - 1 and nums[r + 1] == target:
                    r += 1
                return [l, r]

        return [-1, -1]
  • 执行用时:44 ms,在所有 Python3 提交中击败了 75.48% 的用户。
  • 内存消耗:14.7 MB,在所有 Python3 提交中击败了 6.49% 的用户。

解法 2:两路二分查找法

直接找到 target 的左边界和右边界,相当于两路的二分查找法。左边界的判断标准是自身为 target、左边小于 target,右边界则自身为 target、右边大于 target

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(\log n)$。
  • 空间复杂度为 $O(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
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        lest, rest = -1, -1

        # Find the leftest target
        l, r = 0, length - 1
        while l <= r:
            m = int((l + r) / 2)
            if nums[m] == target and (m == 0 or nums[m - 1] < target):
                lest = m
                break
            if nums[m] >= target:
                r = m - 1
            else:
                l = m + 1

        # If not found
        if lest == -1:
            return [-1, -1]

        # Find the rightest target
        l, r = lest, length - 1
        while l <= r:
            m = int((l + r) / 2)
            if nums[m] == target and (m == length - 1 or nums[m + 1] > target):
                rest = m
                break
            if nums[m] <= target:
                l = m + 1
            else:
                r = m - 1

        return [lest, rest]
  • 执行用时:64 ms,在所有 Python3 提交中击败了 55.31% 的用户。
  • 内存消耗:14.6 MB,在所有 Python3 提交中击败了 6.49% 的用户。