剑指 Offer 53 - I. 在排序数组中查找数字 I

1：问题描述

来源：LeetCode

难度：简单

---

问题详情：
统计一个数字在排序数组中出现的次数。

示例 1:

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

示例 2:

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

---

2：问题分析

2.1 时间复杂度和空间复杂度

在真正开始介绍各种算法前，先以表格形式展示各自的时间复杂度和空间复杂度，其中$n$表示数组nums的长度。

2.2 暴力法

2.2.1 代码

暴力法没有什么技术含量，因此直接给出代码：

def search(self, nums: List[int], target: int) -> int:
    result = 0
    for item in nums:
        if item == target:
            result += 1
    
    return result
1
2
3
4
5
6
7

时间复杂度为$O(n)$,空间复杂度为$O(1)$

2.3 二分查找

对于有序数组的搜索问题，自然需要考虑二分查找。

1. 我们首先使用二分查找找到target最先出现的索引left；
2. 然后使用二分查找找到target最后出现的索引right；
3. 然后返回right-left+1即可。

2.3.1 二分查找第一次出现的索引

def findFirstElement(nums, target):
    """target第一次出现的位置"""
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        # 如果<， 则表示[left,mid]中没有target
        if nums[mid] < target:
            left = mid + 1
        # 如果 > , 则表示[left, mid-1]中存在target
        # 如果 = , 则表示[left, mid]中存在target
        # 为了统一代码，将[left, mid-1]扩大至[left, mid]   
        else:
            right = mid

    # 当循环结束时，left = right，但是也有可能仍然没有找到target
    if nums[left] == target:
        return left
    return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.3.2 二分查找最后一次出现的索引

def findLastElement(nums, target):
    """target最后一次出现的位置"""
    left, right = 0, len(nums) - 1
    while left < right:
        # left与right只相差1的时候，容易陷入死循环,因此此时mid = (left+right)//2 仍旧=left
        # 如果此时有nums[mid]<=target, 那么left = mid = left, 这样一来left和right都没发生变化
        # 而进行上取整后，mid=right,即使有nums[mid]<=target，left=mid=right,那么left=right也能结束循环
        # 如果有nums[mid]>target,right=mid-1=left，那么仍旧结束循环。
        mid = (left + right + 1) // 2
        if nums[mid] <= target:
            left = mid
        else:
            right = mid - 1
    # 由于我们已经找到了第一次出现的位置，
    # 所以最后一次出现的位置最不济也就是第一次出现的位置，不可能出现没找到的情况
    # 因此直接返回left即可
    return left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.3.3 最终代码

def search(nums: List[int], target: int) -> int:
    def findFirstElement(nums, target):
        """target第一次出现的位置"""
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid

        # 当循环结束时，left = right，但是也有可能仍然没有找到target
        if nums[left] == target:
            return left
        return -1

    def findLastElement(nums, target):
        """target最后一次出现的位置"""
        left, right = 0, len(nums) - 1
        while left < right:
            # left与right只相差1的时候，容易陷入死循环,因此此时mid = (left+right)//2 仍旧=left
            # 如果此时有nums[mid]<=target, 那么left = mid = left, 这样一来left和right都没发生变化
            # 而进行上取整后，mid=right,即使有nums[mid]<=target，left=mid=right,那么left=right也能结束循环
            # 如果有nums[mid]>target,right=mid-1=left，那么仍旧结束循环。
            mid = (left + right + 1) // 2
            if nums[mid] <= target:
                left = mid
            else:
                right = mid - 1
        # 由于我们已经找到了第一次出现的位置，
        # 所以最后一次出现的位置最不济也就是第一次出现的位置，不可能出现没找到的情况
        # 因此直接返回left即可
        return left

    if len(nums) == 0:
        return 0
    left = findFirstElement(nums, target)
    if left == -1:
        return 0
    right = findLastElement(nums, target)
    return right - left + 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
36
37
38
39
40
41

时间复杂度为$O(log(n))$,空间复杂度为$O(1)$