LeetCode#189. 轮转数组

这段时间由于发现自己算法题很久没做过了，决定重新开始做一些这些算法题锻炼一下······，后续类似的个人感觉比较有意思的算法题，后续估计都会发到 blog 上 (比较简单的就不发了)

题目如下：

/*
 *  给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 * 示例 1:
 * 输入: nums = [1,2,3,4,5,6,7], k = 3
 * 输出: [5,6,7,1,2,3,4]
 * 解释:
 * 向右轮转 1 步: [7,1,2,3,4,5,6]
 * 向右轮转 2 步: [6,7,1,2,3,4,5]
 * 向右轮转 3 步: [5,6,7,1,2,3,4]
 *
 * 示例 2:
 * 输入：nums = [-1,-100,3,99], k = 2
 * 输出：[3,99,-1,-100]
 * 解释:
 * 向右轮转 1 步: [99,-1,-100,3]
 * 向右轮转 2 步: [3,99,-1,-100]
 *
 * 提示：
 * 1 <= nums.length <= 10^5
 * -2^31 <= nums[i] <= 2^31 - 1
 * 0 <= k <= 105
 *
 * 进阶：
 * 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
 * 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
 */

之前在做这道题的时候，发现不考虑空间复杂度其实问题相当简单，只需要截断数组然后拼接即可。但是如果只考虑空间复杂度是 O(1) 的方案的话，那么问题就会复杂很多。

解决思路

不难看出，如果我们不能新建任何数组来解决 (自然不能截断数组) 的话，那么我们只能通过交换的方式来解决这个位置偏移的问题。而具体的偏移要怎么写，有点无从下手，最简单的方式当然是搞几个例子看一下。

例子1: nums = [1,2,3,4,5,6,7], k = 3
显然最终目标是：[5,6,7,1,2,3,4]，如果完全通过 swap 交换 (被交换结果的值，因为在 temp 中，因此必须在下一次交换中处理) 来完成，那么实际上需要做 7 次交换来完成。

index:
0 -> 3
3 -> 6
6 -> 2
2 -> 5
5 -> 1
1 -> 4
4 -> 0

看起来似乎直接等于 arr.length ，当然只有一个 demo 来看肯定是不行的，我们继续找几个 demo 看看。

例子2：nums = [-1,-100,3,99], k = 2
显然需要的结果是：[3,99,-1,-100]，在完全通过 swap 交换的方式来完成处理的话，那么实际上需要 4 次交换。

index:
0 -> 2    1 -> 3
2 -> 0    3 -> 1

但是跟例子1对比，显然有所不同，要完成两次交换回环，我们才能完成整个目标数组的偏移工作。从这个例子我们已经可以很明显的看出来，实际上这道题必然是在 m 个交换回环中，通过 arr.length 次交换来完成偏移。

交换回环的 m 到底是怎么算出来的？

从现在的信息来看，似乎还不太能推导出这个 m 到底是什么？最快的方法当然是继续多写两个示例，看规律。

例子3：nums = [1,2,3,4,5,6] k = 4
需要的结果是：[3,4,5,6,1,2] ，当然，在完全通过 swap 交换的方式来完成处理的话，那么实际上需要 6 次交换。

index:
0 -> 4	1 -> 5
4 -> 2	5 -> 3
2 -> 0	3 -> 1

这个 demo 回环是 2，，而回环中交换数为 3。

例子4: nums = [1,2,3,4,5,6] k = 3
需要的结果是：[4,5,6,1,2,3,]

index:
0 -> 3	1 -> 4	2 -> 5
2 -> 0	4 -> 1	5 -> 2

在这个 demo 之中，我们的交换回环直接变成了 3，而回环中交换数为 2 。很明显这个是一个非常关键的信息。

Summary

显然，这个回环的个数，必然是取决于 arr.length 和 k 的取值的，这一点从 例子3 和 例子4 就能看出来。
如果 arr.length 是 7 ，k 是 3 那么回环是 1，回环交换数 7
如果 arr.length 是 4 ，k 是 2 那么回环是 2，回环交换数 2
如果 arr.length 是 6 ，k 是 4 那么回环是 2，回环交换数 3
如果 arr.length 是 6 ，k 是 3 那么回环是 3，回环交换数 2
······
从上面这个规律，我们可以得到一个公式，它的本质意思也很好理解，其实就是在计算 经过多少次长度为 k 的元素偏移，才能完整走完整个 arr 中元素，也就是 length 。

回环交换数 * k = arr.length * 回环数

既然 也就是回环交换数为 n ，我们可以进一步演变这个公式变为 -> n * k % length = 0，用以快速计算回环交换数 / 回环数
n * 3 mod 7 = 0 -> 显然只有 n = 7 的时候，才能满足该条件
n * 2 mod 4 = 0 -> 显然只有 n = 2 的时候，才能满足该条件
······

通过这个公式获得具体的 回环数 / 回环交换数 之后，我们就可以以 回环数 作为循环次数，内部只需要确保回到交换的起点即可。而显然的，如果我们要算出来这两个的值，必然需要知道 k 和 arr.length 两者的最小公倍数。

	// 最大公约数
	public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
	// 根据最大公约数算出两者的最小公倍数
    public static int lcm(int a, int b) {
        return a * (b / gcd(a, b));
    }

将我们的最小公倍数代入公式，便可轻松得到我们一直寻求的，回环数和回环交换数。

Answear

class Solution {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static int lcm(int a, int b) {
        return a * (b / gcd(a, b));
    }

    public void rotate(int[] nums, int k) {
        if ( k == 0 )
            return;
        else {
            int lcm = lcm(nums.length, k);
            // 算出需要几次循环
            int count = nums.length / (lcm / k);
            for (int i = 0; i < count; i++) {
                exchange(nums, k, i);
            }
        }
    }

    private static void exchange(int[] nums, int k, int start) {
        int end = (start + k) % nums.length;
        int temp = nums[start];
        int temp1;

        while ( end != start ){
            temp1 = nums[end];
            nums[end] = temp;
            temp = temp1;
            end = (end + k) % nums.length;
        }
        nums[end] = temp;
    }
}