剑指offer二刷——数组专题——数字在升序数组中出现的次数

题目描述

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

我的想法

完整的解法我只想到了遍历数组然后依次统计，但这是不聪明的解法，而且没有利用上“升序数组”的这个条件。

题目标签有提醒可以用二分法解，我想起了大概的思路，但是写不出完整的代码。所以，算法题还是要多刷几遍才行呀，要熟悉解题思路和实现的代码。

这道题给了一个升序数组，一种情况是目标数字出现了至少一次，另外一种情况是目标数字不存在。

没想到的解法二分

给目标数字集合定义一个上边界和一个下边界。

下边界：升序数组中出现的第一个目标数字；如果数组中不存在目标数字，那么选择比目标数字大的第一个数作为下边界。

上边界：不论升序数组中是否存在目标数字，选择比目标数字大一位的数作为上边界。

最后，上边界-下边界，得到的结果就是该数字在升序数组中出现的次数。如果不存在目标数字，那么上下边界都指向比目标数字大一位的数，结果为0。

# -*- coding:utf-8 -*-

class Solution:

    def GetNumberOfK(self, data, k):

        # write code here

        l,r=0,len(data)

        lbound,rbound=0,0

        #寻找下边界

        while l<r:

            mid=l+(r-l)/2

            if data[mid]<k:

                l=mid+1

            else: r=mid

        lbound=l

        #寻找上边界

        l,r=0,len(data)

        while l<r:

            mid=l+(r-l)/2

            if data[mid]<=k:

                l=mid+1

            else: r=mid

        rbound=l

        return rbound-lbound

　时间复杂度o(logn) 空间复杂度o(1)

写代码时，得到上下边界的过程中，如果 data[mid]=k，左右指针的取值是需要注意的。

计算下边界时，当 data[mid]=k，应该让 r=mid；

计算上边界时，当 data[mid]=k，应该让 l=mid+1。

巴特西

剑指offer二刷——数组专题——数字在升序数组中出现的次数

题目描述

我的想法

没想到的解法二分

最新文章

热门文章

巴特西

剑指offer二刷——数组专题——数字在升序数组中出现的次数

题目描述

我的想法

没想到的解法 二分

最新文章

热门文章

没想到的解法二分