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

125 阅读 0 评论 83 点赞

我是靠谱客的博主年轻雪糕，这篇文章主要介绍LeetCode-剑指 Offer 53 - I-在排序数组中查找数字 I剑指 Offer 53 - I. 在排序数组中查找数字 I，现在分享给大家，希望可以做个参考。

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

题目说明

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

示例

复制代码

1
2
3
4
5
6
7
8
输入: 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
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
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)