力扣189、轮转数组

题目

给你一个数组，将数组中的元素向右轮转 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 <= 105
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 105

思路

• 显而易见，k居然周期性，k大于数组长度时就重复翻转了。
• 通过观察，可以发现轮转k个位置，就是把后面k个数放到前面来
• 我们可以翻转整个数组，然后翻转前面k个数，再翻转后面剩余的数。

题解1

#define swap(a, b) \
    (a) ^= (b), (b) ^= (a), (a) ^= (b)

void reverseArray(int *arr, int start, int end) {
    int l = start, r = end;
    while (l < r) {
        swap(arr[l], arr[r]);
        ++l;
        --r;
    }
    return ;
}
void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    if (k == 0) return ;

    reverseArray(nums, 0, numsSize - 1);
    reverseArray(nums, 0, k - 1);
    reverseArray(nums, k, numsSize - 1);
    return ;
}

题解二

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
#define swap(a, b) \
    (a) ^= (b), (b) ^= (a), (a) ^= (b)


void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    if (k == 0) return ;

    int gc = gcd(k, numsSize);

    for (int i = 0; i < gc; ++i) {
        int pi = i;
        int p = nums[i];
        do {
            int ne = (pi + k) % numsSize;
            swap(nums[ne], p);
            pi = ne;
        } while (i != pi);
    }

    return ;
}