美文网首页
offer053在排序数组中查找数字 I

offer053在排序数组中查找数字 I

作者: D_w | 来源:发表于2022-03-17 18:26 被阅读0次

统计一个数字在排序数组中出现的次数。

示例 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

相关文章

网友评论

      本文标题:offer053在排序数组中查找数字 I

      本文链接:https://www.haomeiwen.com/subject/wqxbdrtx.html