比较两个列表，看看其中一个是否为另一个的旋转。

Question

通过一个常见的面试问题清单，这是下一个。对绩效和改进有什么建议吗？怎样才能更好地实现这一目标？还有，如果我错了，这将是\O(N)\$复杂性？

'''
Problem statement: Given 2 integer arrays, determine if the 2nd array is a     rotated version of the 1st array. 
Ex. Original Array A={1,2,3,5,6,7,8} Rotated Array B={5,6,7,8,1,2,3} 

@author: Anonymous3.1415
'''

#@cmp_arr, is the array being compared to see if it is a rotation
def is_rotated(int_arr, cmp_arr):

    #lengths of arrays are the same and not equal to zero?
    if len(int_arr) != len(cmp_arr) or len(int_arr) == 0:
        return False

    #does array contain same numbers?
    if not set(int_arr) <= set(cmp_arr) and not set(int_arr) >= set(cmp_arr):
        return False

    #Find start of first list in the second
    index = 0
    while int_arr[0] != cmp_arr[index]:
        index += 1

    #split list at index point, compare the lists
    cmp_arr = cmp_arr[index:] + cmp_arr[:index]
    index = 0
    for x in int_arr:
        if x != cmp_arr[index]:
            return False
        index += 1

    return True

int_arr = [1,2,3,4,6,4,7]
cmp_arr = [6,4,7,1,2,3,4]
print(is_rotated(int_arr, cmp_arr))

Answer 1

命名

您的2个数组的使用方式相同，为它们设置两个不同的名称有点奇怪。也许int_arr1和int_arr2会是更好的名字。另外，它们包含整数的事实可能与命名无关：arr1和arr2将起作用(或者lst1和lst2，因为对应的D4原始数据结构是list)。

长度检查为0的Problem

检查相同的长度作为函数的开头是一个很好的触摸。

然而，or len(lst1) == 0的情况让我感到不安。只有当检查的第一部分是假的，第二部分是真的，这意味着：len(lst1) == len(lst2) == 0，它真正的意思是：lst1 == lst2 == []时，情况才会有所不同。

我希望空数组是空数组的旋转。另一种方法是记录函数，精确地说明只考虑非平凡的旋转(目前情况并非如此)。简单的解决方法可能是删除此测试或在这种情况下返回True (或者何时使用lst1 == lst2)。

<#>注释

注释代码很好，但是添加明显的注释对任何人都没有帮助。在太多的评论和没有足够的评论之间有一个细微的界限。

举个例子，我会摆脱#lengths of arrays are the same and not equal to zero?。

另一方面，#@cmp_arr, is the array being compared to see if it is a rotation是可以保留的。这应该在函数docstring中移动。而且，Python有一个名为PEP 257的Docstring约定。你可以写：

def is_rotated(lst1, lst2):
    """Test whether list lst1 is a rotation of list lst2."""

Same值多次计算

您需要多次计算set(lst1)，但计算效率不如它所能做到的那样高(这对于打算进行优化的事情来说是可悲的)。

#does array contain same numbers?
s1 = set(lst1)
s2 = set(lst2)
if not s1 <= s2 and not s1 >= s2:
    return False

Optimisation不工作

我想优化的目的是检测以下情况：

lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
print(is_rotated(lst1, lst2))

lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
print(is_rotated(lst1, lst2))

不幸的是，没有检测到这一点。

我猜不是not s1 <= s2 and not s1 >= s2，您的意思是：not s1 <= s2 or not s1 >= s2，它相当于not (s1 <= s2 and s1 >= s2)，它相当于更直截了当的：s1 != s2。

无论如何，正如奥斯卡·史密斯( Oscar Smith )所指出的，这种优化可能不值得去做。

Reusing现有函数

查找索引可以使用已经存在的函数：index = lst2.index(lst1[0])。

Loop就像本机

你的最后一个循环不是毕多诺的。在大多数情况下，在Python中，您可以避免混淆索引。我高度推荐奈德·巴奇尔德的谈话：“活生生的本地人”。

在您的情况下，我们可以在多个步骤中改进您的代码。(在您的例子中，有些步骤是相当人工的，但我使用它们来向您展示Python工具箱中的不同函数)。

引入enumerate以摆脱跟踪index的代码：

#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
for i, x in enumerate(lst1):
    if x != rot2[i]:
        return False
return True

使用zip避免按索引访问rot2：

#split list at index point, compare the lists
rot2 = lst2[index:] + lst2[:index]
for x1, x2 in zip(lst1, rot2):
    if x1 != x2:
        return False
return True

使用all使事情更加简洁：

return all(x1 == x2 for x1, x2 in zip(lst1, rot2))

最后的启示是:所有这些都不需要：

return lst1 == rot2

此时，代码如下所示：

def is_rotated(lst1, lst2):
    """Test whether list lst1 is a rotation of list lst2."""
    if len(lst1) != len(lst2):
        return False

    if lst1 == lst2:
        return True

    if set(lst1) != set(lst2):
        return False

    index = lst2.index(lst1[0])

    #split list at index point, compare the lists
    rot2 = lst2[index:] + lst2[:index]
    return lst1 == rot2

Broken代码

正如奥斯卡·史密斯指出的那样，你的代码不起作用。

对于这种编程任务，编写测试以帮助您捕捉问题是非常容易的。可以在编写代码之前、期间和之后编写这些代码。您可以使用适当的测试框架或简单的断言，如：

# rotation
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,7,1,2,3,4]
assert is_rotated(lst1, lst2)

# rotation with repeated numbers
lst1, lst2 = [1,2,3,4,6,4,7,1], [6,4,7,1,1,2,3,4]
assert is_rotated(lst1, lst2)

# different set
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
assert not is_rotated(lst1, lst2)

# equal
lst2 = lst1
assert is_rotated(lst1, lst2)

# empty
lst1, lst2 = [], []
assert is_rotated(lst1, lst2)

# 1 empty, 1 not empty
lst1, lst2 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)

Answer 2

虽然这是O(n)，但它的速度并不像可能的那么快。

您的第一次检查是一个好的，因为它是O(1)，并将击中随机列表一个公平的数量。然而，第二种情况并非如此。通过找到唯一的元素，您最终完成了一个花费与解决实际问题相当的时间的屏幕。

您的下一段代码实际上被破坏了，因为它只找到第一个匹配，而不是所有可能的匹配。事实上，当您修复这个bug时，您的代码在最坏的情况下将是O(n^2) (如果一个是[0]*1000+[1,0]，另一个是[0]*1000+[0,1])。