C++ 数组旋转的 Juggling 算法

杂耍算法是一种有用的C++技术，通过移动元素来实现旋转。它使用数组大小 n 和旋转位置 d 的最大公约数 (GCD) 将数组分成若干组。之后，元素被循环移动，以独立旋转这些组中的每个组。它确保所有元素都被移动，但无需额外内存。当 n 是数组大小时，其时间复杂度为 O(n)，空间复杂度为 O(1)。在数组较大且内存有限的情况下，它是一种非常可行的原地旋转。

杂耍算法的核心概念

杂耍算法基于两个参数：数组长度 n 和旋转位置 d 的最大公约数 (GCD)。其用法如下：将数组分解为要旋转的元素部分。n 和 d 的 GCD 决定了计算的组数。

杂耍算法步骤

• GCD 计算：为了计算 GCD，需要找到数组大小 n 和旋转次数 d 的 GCD。
• 将数组分成组：可以将数组中的所有元素视为循环的组成部分。对于 n 和 d，GCD 是总组数。在杂耍过程中，每组组件都在数组内移动。
• 旋转组中的元素：从每组中一次取一个元素，将其重新定位到新位置，并重复此过程，直到覆盖所有可能区域。

如果大小为 n 的数组旋转 d 个位置，会产生多少个独立循环？

大小为 n 的数组旋转 d 个位置，其独立循环数与 gcd(n, d) 相等。循环从开头开始并增加，因为我们以 d 的步长旋转数组。因此，每个循环中移动的总距离将是 n 的倍数，或 lcm(n, d)。因此，每个循环中的元素数量等于 lcm(n, d)/d。覆盖所有 n 个元素所需的总循环数将是 n/lcm(n, d) = gcd(n, d)。

示例

以下过程可用于将包含七个项目 [1, 2, 3, 4, 5, 6, 7] 的数组旋转 d = 2 个位置。

1. 首先计算 7 和 2 的 GCD，结果是 1。
2. 将旋转数组中的第一个元素移动到其正确位置是移动下一个元素的第一个步骤，依此类推，完成数组中的一个循环。

示例

让我们举一个例子来说明 C++ 中的杂耍算法或数组旋转。

输出

 
3 4 5 6 7 1 2   

说明

• gcd() 函数还有助于通过提供最大旋转组数来确定数组必须旋转的最大次数，该组数使用 gcd() 函数提取。
• 在 RotateArray() 函数中，对象向量和矩阵的角旋转是在其自身平面中从坐标到坐标执行操作的，在这种情况下，部分内容在平面中循环移动，以执行所需 d 位置的角位移。
• 如上所述，时间复杂度为 O(n)，其中 n 表示数组中的项目数。
• 过程中只涉及变量，因此空间复杂度是常数，即 O(1)。

结论

总之，杂耍算法是旋转数组最有效的技术，因为它可以在原地完成并且需要最小的内存开销。特别是，该技术通过使用 GCD 方法估计总块移位数，促进以最小移位寄存器要求移动对象。由于其时间复杂度为 O(n) 且空间复杂度为 O(1)，该技术也适用于内存受限的应用，例如嵌入式系统或大型数据集。逻辑划分项目并围绕旋转的内在特性确保这是 C++ 编程语言中数组操作的强大而灵活的策略。