使用 Python 在另一个列表中搜索列表 [英] search a list in another list using Python

问题描述

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

I am trying to write the sublist search algorithm using 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)增加?初学者在这里

I am sure this code can be optimized and reduce time complexity. Because of while loop, does the complexity increase than O(m*n)? Beginner student here

推荐答案

我认为这样效果更好:

def sublist(arr1,arr2):
  "This fuction checks if arr1 is a sublist of arr2."
  for i in range(len(arr2)):
    part=arr2[i:] # part is a list which all the elements from i to the end of arr2
    if len(part)<len(arr1):
      return False
    if arr1==part[:len(arr1)]: # if arr1 is in the beginning of part return True
      return True
  return False

这篇关于使用 Python 在另一个列表中搜索列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！