每日一题-3rd

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

---

Leetcode 189. 轮转数组

题干

给定一个整数数组 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]

思路

最容易的、最好想的方法是遍历法（O(n)时间、O(1)空间）：

随机取出一个位置上的值（以第一个为例），储存，计算它变换后的位置，提前计算变换后位置上的值的变换后的位置，交换变换后的位置上的值和取出的值，发现规律：如果按照上面的移动替换方法，那么元素移动最终会结成一个个循环的圈，这些圈的个数：cnum = GCD(len, k)，这些圈长度：clen = len / cnum。

这样对于每个圈中的元素循环移动一周，就能完成更换。

实现

class Solution {
public:
    int GCD(int a, int b) {
        if (a < b) { a = a ^ b; b = b ^ a; a = a ^ b; }
        if (a % b == 0 || b == 0) return b;
        else return GCD(b, a % b);
    }
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        k %= len; if (!k) return;
        int circleNum = GCD(len, k), circleLen = len / circleNum;
        int tmp = nums[0], idx = 0;
        for (int i = 0; i < circleNum; ++i) {
            tmp = nums[i]; idx = i;
            for (int j = 0; j < circleLen; ++j) {
                idx = (idx + k) % len;
                swap(tmp, nums[idx]);
            }
        }
    }
};