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

题目说明

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

示例

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



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

题解思路

  两种做法
1、使用哈希表：
  遍历数组，如果存在于表中，值加一；如果不存在，设置键值对，键为该元素，值为1
2、二分法
  使用i和j指向头和尾，如果m=（i+j）//2 (向下取整)位置的元素大于target，说明target在中间值的左边，那么j=m-1；否则，说明target在中间值的右边，那么i=m+1
循环跳出条件：i > j

代码实现

1、哈希
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        dic = dict()
        for i in nums:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        if target in dic:
            return dic[target]
        else:
            return 0


2、二分法
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def helper(tar):
            i, j = 0, len(nums) - 1
            while i <= j:
                m = (i + j) // 2
                if nums[m] > tar:
                    j = m - 1
                else:
                    i = m + 1
            return i
        return helper(target) - helper(target - 1)

最后

以上就是年轻雪糕为你收集整理的LeetCode-剑指 Offer 53 - I-在排序数组中查找数字 I剑指 Offer 53 - I. 在排序数组中查找数字 I的全部内容，希望文章能够帮你解决LeetCode-剑指 Offer 53 - I-在排序数组中查找数字 I剑指 Offer 53 - I. 在排序数组中查找数字 I所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。