[百度面试题]数组A中任意两个相邻元素大小相差1,在其中查找某个数。


数组A中任意两个相邻元素大小相差1,现给定这样的数组A和目标整数t,找出t在数组A中的位置。
如数组:[1,2,3,4,3,4,5,6,5],找到4在数组中的位置。
这道题目最差时间复杂度也是O(N),所以重点在于能不能找到一种尽可能减少比较次数的方法。@jefflee 的方法就很不错,但感觉应该还可以继续优化?
已邀请:

根据 @Menson 建议优化

    if ( A[0]-t ) % 2 != 0:
        i = 1
    else:
        i = 0
    while i < len(A):
        if A[i] == t:
           break
        i += max( abs(A[i]-t), 2 )

最坏时间复杂度 O(N): 如在 [1,2,1,2,1,2,1,2,1,0] 里找0

要回复问题请先登录注册

返回顶部