数字在升序数组中出现的次数
数字在升序数组中出现的次数
问题描述
给定一个长度为 n 的非降序数组和一个非负数整数 k ,要求统计 k 在数组中出现的次数是多少。
示例:
输入:[1,2,3,3,3,3,4,5],3
输出:4
分析问题
不管给定的数组是否是有序的,如果要查找数组中是否存在某个元素,我们只需要对数据进行一次遍历即可。下面,我们来看一下代码的实现。
class Solution: def GetNumberOfK(self,data, k): n=0 for x in data: if x==k: n=n+1 return n复制代码
该算法的时间复杂度是O(n),其中n代表数组中元素的个数。空间复杂度是O(1)。
因为题目给定的数组是有序的,所以我们可以使用二分查找来求解。对于有序的数组,如果要寻找的目标值target有多个,那么他们肯定是连在一起的,所以我们可以通过二次二分查找,分别寻找目标值所在范围的上界和下界。首先,我们来看一下上界和下界的定义。
下界定义为:如果存在目标值,则指向第一个目标值;如果不存在, 则指向大于目标值的第一个值。
上界定义为:不管目标值存在与否,都指向大于目标值的第一个值。
下面我们来看一下代码实现。
class Solution: def GetNumberOfK(self,data, k): l=0 r=len(data)-1 #二分法寻找下界 while l<r: mid = (r+l) // 2 if data[mid] < k: l = mid + 1 else: r = mid left=l #寻找上界 l = 0 r = len(data)-1 while l<r: mid=(r+l)//2 if data[mid] <= k: l=mid+1 else: r=mid right=l return right - left复制代码
该算法的时间复杂度是O(logN),其中n是数组中元素的个数。空间复杂度是O(1)。
作者:程序员学长
链接:https://juejin.cn/post/7028119101197254669