剑指Offer53-I-在排序数组中查找数字I
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示：
-
0 <= nums.length <= 10^5
-
-10^9 <= nums[i] <= 10^9
-
nums 是一个非递减数组
-
-10^9 <= target <= 10^9
来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
使用二分法：使用二分法找到“目标数字”的下一位位置和“目标数字 - 1”的下一位位置，比如下图：
因此 8 在数组中出现的次数为：5 - 3 = 2。
class Solution:
def search(self, nums: List[int], target: int) -> int:
def helper(tar):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l)//2
if nums[mid] <= tar: l = mid + 1
else: r = mid - 1
return l
return helper(target) - helper(target - 1)
-
时间复杂度 O(logN)： 二分法时间复杂度。
-
空间复杂度 O(1)。