python - 对我来说最重要的问题 : is there a better way off doing it and if there is, 你们能给我指出正确的方向吗？

Question

我有一个这样的任务。本章中的部分又称为爱丽丝梦游仙境!首先观察到合并算法使用了可以在其他情况下重用的模式。调整合并算法来写这些功能中的每一个，正如其中所建议的:

我需要解决这个问题:A。仅返回两个列表中都存在的项目。

合并算法如下:

def merge(xs, ys):
    """ merge sorted lists xs and ys. Return a sorted result """
    result = []
    xi = 0
    yi = 0

    while True:
        if xi >= len(xs):          # If xs list is finished,
            result.extend(ys[yi:]) # Add remaining items from ys
            return result          # And we're done.

        if yi >= len(ys):          # Same again, but swap roles
            result.extend(xs[xi:])
            return result

        # Both lists still have items, copy smaller item to result.
        if xs[xi] <= ys[yi]:
            result.append(xs[xi])
            xi += 1
        else:
            result.append(ys[yi])
            yi += 1

我解决这个问题的方法是:

def merge(xs, ys):
    """ merge sorted lists xs and ys. Return a sorted result """
    result = []
    xi = 0
    yi = 0

    while True:
        if xi >= len(xs):          # If xs list is finished,
            return result         # And we're done.

        if yi >= len(ys):          # Same again, but swap roles
            return result


        for xi in xs:
            if xi in ys:
                result.append(xi)


xs = [1,3,4,5,7,9,11,13,15,17,19]
ys = [4,5,8,12,16,20,24]
zs = xs+ys
zs.sort()
print(merge(xs, ys))

如果您对有关此问题的更多信息感兴趣，可以在这里找到: http://openbookproject.net/thinkcs/python/english3e/list_algorithms.html

对我来说最重要的问题是:是否有更好的方法，如果有，你们能给我指出正确的方向吗？

Answer 1

您可以在合并列表时简单地检查此条件。这将以 O(n) 时间复杂度返回两个列表中都存在的元素。

xs = [1,3,4,5,7,9,11,13,15,17,19]
ys = [4,5,8,12,16,20,24]

index1 = 0
index2 = 0
result = []
while index1 < len(xs) and index2 < len(ys):
    if xs[index1] == ys[index2]:
        result.append(xs[index1])
        index1 += 1
        index2 += 1
    elif xs[index1] < ys[index2]:
        index1 += 1
    else:
        index2 += 1
print(result)

输出

➜  codebase git:(master) ✗ python temp.py
[4, 5]