python - 查找列表中的第一个符号变化

Question

我有一个整数列表 A，它是这样的：

1. 透镜（A）≥2
2. A 的第一个和最后一个元素有不同的符号
3. A 的所有元素都不为零

我需要编写一个函数来检测第一个和最后一个元素旁边的第一个符号变化以及 O(log n) 的位置。是否可以？

def myFunction(A,begin):
    if(begin >= len(A)):
        return [A[0],A[len(A)-1]]
    if(A[begin]>0):
        if(A[begin+1]>0):
            return myFunction(A,begin+1)
        else:
            return [A[begin],A[begin+1]]
    else:
        if (A[begin + 1] < 0):
            return myFunction(A, begin + 1)
        else:
            return [A[begin], A[begin + 1]]

标签： python

Answer 1

这个解决方案是 O(log N)，因为它将第一个元素与中间元素进行比较，然后只继续列表的前半部分或后半部分。但是，这仅在只有一个符号更改时才有效。

def find_sign_change(A):
    if len(A) == 2:
        return 1
    i = len(A) // 2
    if A[0] * A[i] < 0:
        # different sign
        return find_sign_change(A[:i+1])
    else:
        # same sign
        return find_sign_change(A[i:]) + i


print(find_sign_change([3, 4, 6,-6,-5,-3,-5]))
>>> 3
print(find_sign_change([3,-4, 6, 6, 5, 3,-5]))
>>> 6