统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
python偷鸡解法:
class Solution:
def search(self, nums: List[int], target: int) -> int:
if target not in nums:
return 0
dic = {}
for i in nums:
if i not in dic:
dic[i] = 1
else:
dic[i] = dic[i]+1
return dic[target]
或直接用count
class Solution:
def search(self, nums: List[int], target: int) -> int:
return nums.count(target)
正常解法:
初始化: 左边界 i = 0i=0 ,右边界 j = len(nums) - 1j=len(nums)−1 。
循环二分: 当闭区间 [i, j][i,j] 无元素时跳出;
计算中点 m = (i + j) / 2m=(i+j)/2 (向下取整);
若 nums[m] < targetnums[m]<target ,则 targettarget 在闭区间 [m + 1, j][m+1,j] 中,因此执行 i = m + 1i=m+1;
若 nums[m] > targetnums[m]>target ,则 targettarget 在闭区间 [i, m - 1][i,m−1] 中,因此执行 j = m - 1j=m−1;
若 nums[m] = targetnums[m]=target ,则右边界 rightright 在闭区间 [m+1, j][m+1,j] 中;左边界 leftleft 在闭区间 [i, m-1][i,m−1] 中。因此分为以下两种情况:
若查找 右边界 rightright ,则执行 i = m + 1i=m+1 ;(跳出时 ii 指向右边界)
若查找 左边界 leftleft ,则执行 j = m - 1j=m−1 ;(跳出时 jj 指向左边界)
返回值: 应用两次二分,分别查找 rightright 和 leftleft ,最终返回 right - left - 1right−left−1 即可。
python
class Solution:
def search(self, nums, target: int) -> int:
# return nums.count(target)
i,j = 0,len(nums)-1
while i <= j:
m = (i+j)//2
if nums[m] <= target:
i = m+1
else:
j=m-1
right = i
if j > 0 and nums[j] !=target:
return 0
i=0
while i <= j:
m = (i+j)//2
if nums[m] < target:
i = m+1
else:
j = m-1
left = j
return right-left-1
网友评论