首页 > 代码库 > 【剑指offer】Q38:数字在数组中出现的次数
【剑指offer】Q38:数字在数组中出现的次数
与折半查找是同一个模式,不同的是,在这里不在查找某个确定的值,而是查找确定值所在的上下边界。
def getBounder(data, k, start, end, low_bound = False): if end < start : return -1 while start <= end: mid = ( start + end ) >> 1 if data[ mid ] > k: end = mid - 1 elif data[ mid ] < k: start = mid + 1 else: if low_bound == True: if mid == 0 or data[ mid - 1 ] != k: return mid else: end = mid - 1 else: if mid == end or data[ mid + 1 ] != k: return mid else: start = mid + 1 def getNumberOfk(data, k): if len(data) <= 1: return len(data) low_bound = getBounder( data, k, 0, len( data ) - 1, low_bound = True ) up_bound = getBounder( data, k, 0, len( data ) - 1, low_bound = False) return up_bound - low_bound + 1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。