检查一个列表是否是另一个含有重复元素列表的旋转版本

Question

我有一个用于确定列表是否为另一个列表的旋转的函数：

def isRotation(a,b):
  if len(a) != len(b):
    return False

  c=b*2
  i=0

  while a[0] != c[i]:
    i+=1

  for x in a:
    if x!= c[i]:
      return False
    i+=1

  return True

例如

>>> a = [1,2,3]
>>> b = [2,3,1]
>>> isRotation(a, b)
True

如何使这个工作与重复项一起？例如：

a = [3,1,2,3,4]
b = [3,4,3,1,2]

它可以在O(n)时间内完成吗？

- Rahat Mahbub

---

重复的数量有关系吗？例如 - [1,2,3] 和 [3,1,2,3] 是不同的吗？ - Anand S Kumar

是的，它们肯定是不同的。 - Rahat Mahbub

在这种情况下，保持长度的计数并拒绝匹配，如果它们不同。 - Martin James

旋转数组是将N个元素从一端取出并放置在另一端，而不是任意顺序的洗牌：[1, 2, 3, 4, 5, 6] -> [3, 4, 5, 6, 1, 2]。 - Izkata

非常相关：https://dev59.com/I3E85IYBdhLWcg3w43-o 还有很多类似的问题... - Deduplicator

Answer 1

以下元算法将解决它。

1. 构建一个连接a的串，例如，a = [3,1,2,3,4] => aa = [3,1,2,3,4,3,1,2,3,4]。 2. 运行任何字符串匹配算法的字符串适应性，例如Boyer Moore，以在aa中查找b。

---

我建议您尝试一种特别简单的实现方法，即使用Rabin Karp作为基础算法。在此方法中，您需要：

• 计算b的Rabin指纹

• 计算aa[: len(b)]、aa[1: len(b) + 1]等的Rabin指纹，并仅在指纹匹配时进行列表比较

请注意：

• 滑动窗口的Rabin指纹可以通过迭代计算非常高效（在Rabin-Karp链接中了解更多信息）

• 如果您的列表是整数，那么与字符串相比，您会更容易些，因为您不需要考虑字母的数字哈希值是多少

- Ami Tavory

---

那么，您建议我将其转换为字符串。这听起来不太高效。如果将其转换为字符串，是否有任何想法可以比较O(n^2)解决方案更好？ - Rahat Mahbub

我并不建议你将其转换为字符串，而是建议你为其采用字符串匹配算法。稍后会提供更多细节。 - Ami Tavory

Answer 2

通过修改最大后缀算法的版本，可以在0(n)时间和0(1)空间内完成：

引自《串的珠宝》： 循环等价性

 

长度为n的单词u的旋转是形式为u[k+1...n][l...k]的任意单词。令u、w为长度相同的两个单词，如果存在i、j使得u(i) == w(j)，则它们被称为循环等价。

    

如果将单词u和w写成圆，当圆在适当的旋转后重合时，它们是循环等价的。

    

有几种线性时间算法可用于测试两个单词的循环等价性。最简单的方法是将任何字符串匹配算法应用于模式pat = u和文本text = ww，因为如果pat出现在text中，则单词u和w是循环等价的。

    

另一种算法是找到uu和ww的最大后缀，并检查它们在大小为n的前缀上是否相同。我们选择这个问题，因为有一个更简单的有趣算法，同时在线性时间和常量空间中工作，值得介绍。

Algorithm Cyclic-Equivalence(u, w)
{ checks cyclic equality of u and w of common length n }
    x := uu; y := ww;
    i := 0; j := 0;
    while (i < n) and (j < n) do begin
        k := 1;
        while x[i + k] = y[j + k] do k := k + 1;
        if k > n then return true;
        if x[i + k]> y[i + k] then i := i + k else j := j + k;
        { invariant }
    end;
    return false; 

翻译成Python后变成：

def cyclic_equiv(u, v):
    n, i, j = len(u), 0, 0
    if n != len(v):
        return False
    while i < n and j < n:
        k = 1
        while k <= n and u[(i + k) % n] == v[(j + k) % n]:
            k += 1
        if k > n:
            return True
        if u[(i + k) % n] > v[(j + k) % n]:
            i += k
        else:
            j += k
    return False

运行一些示例：

In [4]: a = [3,1,2,3,4]   
In [5]: b =[3,4,3,1,2]   
In [6]: cyclic_equiv(a,b)
Out[6]: True    
In [7]: b =[3,4,3,2,1]    
In [8]: cyclic_equiv(a,b)
Out[8]: False    
In [9]: b =[3,4,3,2]    
In [10]: cyclic_equiv(a,b)
Out[10]: False
In [11]: cyclic_equiv([1,2,3],[1,2,3])
Out[11]: True
In [12]: cyclic_equiv([3,1,2],[1,2,3])
Out[12]: True

一种更加天真的方法是使用collections.deque来旋转元素：

def rot(l1,l2):
    from collections import deque
    if l1 == l2:
        return True
    # if length is different we cannot get a match
    if len(l2) != len(l1):
        return False
    # if any elements are different we cannot get a match
    if set(l1).difference(l2):
        return False
    l2,l1 = deque(l2),deque(l1)
    for i in range(len(l1)):
        l2.rotate() # l2.appendleft(d.pop()) 
        if l1 == l2:
            return True
    return False

- Padraic Cunningham

---

这里有一个用于比较的C++实现：https://dev59.com/I3E85IYBdhLWcg3w43-o#2732159。 - jfs

Answer 3

我认为你可以使用类似这样的东西：

我认为您可以使用类似以下内容的东西：

a1 = [3,4,5,1,2,4,2]
a2 = [4,5,1,2,4,2,3]

# Array a2 is rotation of array a1 if it's sublist of a1+a1
def is_rotation(a1, a2):
   if len(a1) != len(a2):
       return False

   double_array = a1 + a1

   return check_sublist(double_array, a2)

def check_sublist(a1, a2):
   if len(a1) < len(a2):
       return False

   j = 0
   for i in range(len(a1)):
        if a1[i] == a2[j]:
              j += 1
        else:
              j = 0

        if j == len(a2):
              return True

   return j == len(a2)

如果我们谈论面试问题，这是很常见的道理:

• 我们应该记住解决方案应该易于编码和描述。
• 不要试图在面试时记住解决方案。更好的方法是记住核心原则并重新实现它。

- Jimilian

---

“in”键似乎无法正常工作，而实现对重复项的处理则是我的问题。 - Rahat Mahbub

@RahatMahbub，是的，你说得对，我会修复它。在这个任务中，重复不是问题。 - Jimilian

那么，您建议我将其转换为字符串。这听起来不太高效。如果将其转换为字符串，是否有任何想法可以比较O(n^2)解决方案更好？ - Rahat Mahbub

如果 a1 的长度不等于 a2 的长度，那么它们就无法匹配。因此，a1 可能比 a2 更大。 - Padraic Cunningham

第二个 if len(a1) < len(a2): 是多余的，如果长度相同，那么 a1+a1 不能更小。 - Padraic Cunningham

Answer 4

另一种方法（我无法让“aa中的b”解决方案起作用），您可以“旋转”列表并检查旋转后的列表是否等于b：

def is_rotation(a, b):

    for n in range(len(a)):
        c = c = a[-n:] + a[:-n]
        if b == c:
            return True

    return False

我认为这个代码的时间复杂度是O(n)，因为它只有一个for循环。希望能够帮到你。

- Matthew

---

你忘记了 in 本身就是 O(n) :) - Jimilian

这很酷，但由于b==c，我相信运行时间将是O(n^2)。 - Rahat Mahbub

Answer 5

这似乎是有效的。

def func(a,b):
    if len(a) != len(b):
        return False
    elif a == b:
        return True

    indices = [i for i, x in enumerate(b) if x == a[0] and i > 0]

    for i in indices:
        if a == b[i:] + b[:i]:
            return True

    return False

同时还有这个：

def func(a, b):
    length = len(a)

    if length != len(b):
         return False

    i = 0
    while i < length:
        if a[0] == b[i]:
            j = i
            for x in a:
                if x != b[j]:
                    break
                j = (j + 1) % length
            return True
        i += 1

    return False

- user1602492

Answer 6

如果您可以将它们表示为字符串，只需执行以下操作：

def cyclically_equivalent(a, b):
    return len(a) == len(b) and a in 2 * b

否则，应该使用子列表搜索算法，例如 Knuth-Morris-Pratt（Google 提供了一些实现），并执行。

def cyclically_equivalent(a, b):
    return len(a) == len(b) and sublist_check(a, 2 * b)

- Veedrac

Answer 7

你可以尝试测试仅使用deque集合中的rotate()函数的性能：

from collections import deque

def is_rotation(a, b):

    if len(a) == len(b):
        da = deque(a)
        db = deque(b)

        for offset in range(len(a)):
            if da == db:
                return True

            da.rotate(1)

    return False

在性能方面，您需要为小数组多次进行此计算，还是在非常大的数组上少量进行计算？这将决定是否需要进行特殊情况测试以加快速度。

- Martin Evans

---

这是一个面试问题，所以没有特定的尺寸要求。但是使用 for 循环进行旋转应该会导致 O(n^2) 的时间复杂度。我的算法对于除重复项外的任何输入都是 O(n) 的。 - Rahat Mahbub

Answer 8

Knuth-Morris-Pratt算法是一种字符串搜索算法，其运行时间为O(n)，其中n是文本S的长度（假设存在预构建的表T，其运行时间为O(m)，其中m是搜索字符串的长度）。总体而言，它是O(n+m)。

您可以通过KMP算法获得类似的模式匹配算法。

• 将列表自身连接起来，例如a+a或b+b - 这是具有2*n个元素的搜索文本/列表
• 基于另一个列表（无论是b还是a）构建表T - 这需要O(n)的时间
• 运行受KMP启发的算法 - 这需要O(2*n)的时间（因为您将列表连接到自身）

总体时间复杂度为O(2*n+n)=O(3*n)，即O(n)

- Ely