c - 找出循环序列中的旋转次数

Question

用户给了我两个数组。我的代码应该找出它向左或向右旋转了多少次。我们可以安全地假设元素不会重复。

我/我:

数组 (arr1) 2, 6, 4, 10, 8 ,12 ,11

旋转数组(arr2) 4, 10, 8, 12, 11, 2, 6

对/对:2

方法一:

我解决这个问题的方法是这样的:

1.从旋转数组中取出第一个元素，并从旋转数组中取出最后一个元素。分别将它们命名为“第一个”和“最后一个”。并将计数初始化为0

2.从头开始比较“first”和arr1的元素，直到我们到达arr1中的“first”。同时开始比较"last"和arr1中从末尾开始的元素，一直递减，直到达到与arr1中"last"等价的数。

3.我们可以在step2的同一个for循环中对上面的step 2进行递增和递减，同时递增count变量。

3.就是这样，无论“first”还是“last”中的哪个早点找到它的等价物，然后中断并打印计数。

方法二:

获取 arr2 的第一个元素，并开始将它与末尾的 arr1 元素进行比较，直到找到匹配为止。我们递减arr1的次数就相当于旋转的次数

有没有比以上两种更好的方法？

Answer 1

如果您“可以安全地假设元素不会重复”，那么没有比单步执行 arr1 的元素更好的方法，直到找到 arr2 的第一个元素。你必须做的步数是你的左旋转。您可以通过从任一数组的长度中减去左旋转并减去 1 来计算右旋转。