检查两个数组是否为循环排列

Question

给定两个数组,如何检查一个是否是另一个的循环排列？

例如,给定a = [1, 2, 3, 1, 5],b = [3, 1, 5, 1, 2]和,c = [2, 1, 3, 1, 5]我们有,a并且b是循环排列,但c不是两者的循环排列.

注意:数组可能包含重复元素.

Answer 1

这里的标准技巧是将其中一个数组与自身连接起来,然后尝试在连接数组中找到第二个数组.

例如,与自身连接的'a'是:

[1,2,3,1,5,1,2,3,1,5]

因为你从第3个元素开始看到这个数组中的'b',所以a和b是循环排列.

Answer 2

如果A和B是彼此的循环排列,则A将在双重列表BB中找到(与AA中的B一样).

Answer 3

处理大量数据的有效方法是将每个数据转换为"规范"形式,然后比较它们是否相等.对于这个问题,您可以选择所有旋转排列的规范形式,即"最小排序".

因此,'a'和'b'的规范形式是[1,2,3,1,5],它们是相等的,因此它们是非循环排列.

'c'的规范形式是[1,3,1,5,2],这是不同的.