Find k-th Rotation of an Array in Java

旋转是计算机科学中的一个核心问题，在这种情况下，我们要对数组的元素进行逆时针旋转。这两种可以是左旋转，其中元素向左移动，使第一个元素成为列表的最后一个；或者右旋转，其中元素向右移动，最终使最后一个元素成为列表的第一个。

示例

左旋转： 假设我们旋转 [1, 2, 3, 4, 5] 中的元素两次，得到 [3, 4, 5, 1, 2]，这两项都指给定的列表。

右旋转： 假设我们使用上述方法，对于一个旋转了 2 次的 整数 数组 [1, 2, 3, 4, 5]，我们得到 [4,5,1,2,3]。这个问题既可以用暴力法也可以用最优法解决，并且肯定会讨论其中的每一种。

暴力破解法

执行旋转的最简单方法是为 k 次旋转逐个重复地移动数组的元素。

在左旋转中，每次传递后将第一个元素移到最后，传递包括总的循环跟踪和迭代。

要执行右旋转，将最后一个元素重新排列到数组第一个右边的位置。

步骤：

• 在旋转中，对所讨论数据结构中的所有元素进行一次性处理。
• 重复该过程 k 次。

时间复杂度： O(k × n)，其中 k 是旋转次数，n 是数组大小。每次旋转都需要移动所有 n 个元素。

空间复杂度： O(1)（原地）。

暴力法的缺点

效率低下： 随着 k 的增加，重复移动变得繁琐，因此需要找到一种最优的解决方案来处理所有移动。

冗余操作： 有些旋转是不必要的，因为它们可能会完成一个大小为 n 的数组的循环（例如，可以将数组旋转 n 次）。

最优方法

我们可以一步完成旋转，而不是执行多次移动。

1. 在此之前，通过使用模运算 (k % n) 来确定有效旋转次数，因为最终 n 次旋转会使你回到起始数组。
2. 根据旋转索引将数组分成两部分。
   
   • 左旋转：在索引 k 处拆分。
   • 右旋转：在索引 n - k 处拆分。
3. 重新排列这些部分以形成旋转后的数组。
   
   • 将第二部分与第一部分连接起来。

算法

1. 由于在操作中总是 k > n，因此使用 k = k % n 来处理它。
2. 使用数组切片进行拆分和合并。
   
   • 左旋转：[k..n-1] + [0..k-1]。
   • 右旋转：[n-k..n-1] + [0..n-k-1]。

文件名：ArrayRotation.java

输出

 
Original Array: [1, 2, 3, 4, 5]
Left Rotated by 2: [3, 4, 5, 1, 2]
Right Rotated by 2: [4, 5, 1, 2, 3]   

时间复杂度： O(n)，其中 n 是数组的大小。System.arraycopy 函数 以 O(n) 的效率复制数组片段。

空间复杂度： O(n)，因为我们为结果创建了一个新数组。

结论

我们探讨了两种解决 k 次旋转问题的方法：暴力法和优化法。暴力法的策略是重复移动元素，需要 k × n 的时间才能完成，因此不适用于大型数组旋转或大量旋转。

然而，优化解决方案利用模运算和数组切片以 O(n) 的时间完成类似的结果。这种改进意味着该解决方案具有可扩展性，并且足够高效，可以应用于实际程序和竞争性编程。