时间戳

首页 > 解决方案 > 使用 Python 在另一个列表中搜索列表

python-3.x - 使用 Python 在另一个列表中搜索列表

问题描述

我正在尝试使用 Python 编写子列表搜索算法。

供参考： https ://www.geeksforgeeks.org/sublist-search-search-a-linked-list-in-another-list/

这是我的代码：

def sublist(arr1,arr2):
i = 0
j = 0
k = 0
if len(arr1) == 0:
    print('List1 Empty')
if len(arr2) == 0:
    print('List 2 Empty')
for j in range(0,len(arr2)):
    for i in range(0,len(arr1)):
        if arr1[i] != arr2[j]:
            break
        while arr1[i] == arr2 [j]:
            if i == len(arr1) - 1:
                return True
            i = i + 1
            j = j + 1
            if i == len(arr1):
                return False
        return False

我确信这段代码可以优化并降低时间复杂度。由于while循环，复杂度是否比O（m * n）增加？初学者在这里

标签： python-3.xalgorithmtime-complexitysublist

解决方案

下面比较 to 的第一部分arr2，arr1以确定它们是否相等。如果是这样，或者对某个偏移量的任何递归调用都arr2返回 true，则返回 true。否则，如果在任何时候原始的子列表arr2短于arr1，则返回 False。

def sublist(arr1, arr2):
    if len(arr2) < len(arr1):
        return False
    return arr1 == arr2[:len(arr1)] or sublist(arr1, arr2[1:])

推荐阅读