如何在python中以给定的时间复杂度从两个数组中找到最小元素

Question

我有2个数组A和B.我试图从数组A和B中常见的元素中找到最小值.

喜欢,如果A = [1,3,2,1]&B = [4,2,5,3,2],那么它应该返回,2因为它是A和B中的最小元素.我的代码适用于这种情况,但在某些情况下它不起作用.我不知道如何解决它.请帮忙!

def findMin(A, B):
    A.sort()
    B.sort()
    i = 0
    for x in A:
        if i < len(B) - 1 and B[i] < x:
            i += 1
        if x == B[i]:
            return x
    return -1

此外,我希望最坏的情况时间复杂度 O((N+M)*log(N+M))

Answer 1

你在那里投掷你并不真正需要的那种,找到两者的交集使用一套,然后采取最小...

>>> A = [1,3,2,1]
>>> B = [4,2,5,3,2]
>>> min(set(A).intersection(B))
2

哪个会使你的功能:

def findMin(A, B, default=-1):
    return min(set(A).intersection(B), default=default)

如果两个列表之间没有交集(你似乎选择了-1),则默认参数是返回的内容,但这是Python 3.x的补充,如果你坚持使用Python 2.x,你需要处理它通过例外,例如:

def findMin(A, B, default=-1):
    try: 
        return min(set(A).intersection(B))
    except ValueError:
        return default

至于复杂性,最坏的情况是O(len(A) * len(B))交叉点,虽然平均情况是O(min(len(A), len(B))(见时间复杂度),然后min你需要添加的操作是O(N).