C语言解读数组循环右移问题

C语言解读数组循环右移问题攻略

1. 问题描述

在数组中，循环右移操作是将数组中的元素向右移动k个位置，其中k为移动的步数，当移动到最后一个元素时，需要将最后一个元素的值作为第一个元素的值。如：[1, 2, 3, 4, 5]，循环右移3个位置后变为[3, 4, 5, 1, 2]。

2. 解题思路

循环右移的本质是将原数组分为两部分：左边为需要右移的部分，右边为不需要右移的部分。
将左边需要右移的部分先进行反转，再将右边不需要右移的部分进行反转，最后将整个数组进行反转，即可得到循环右移后的结果。

令数组为nums，数组长度为n，需要右移的步数为k。

反转操作

定义reverse函数，实现反转操作：

void reverse(int* nums, int start, int end) {
    while(start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}

循环右移操作

1. 对左边的部分进行反转，反转范围为[0, n-k-1]
2. 对右边的部分进行反转，反转范围为[n-k, n-1]
3. 对整个数组进行反转，得到循环右移后的结果

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
    reverse(nums, 0, numsSize-k-1);
    reverse(nums, numsSize-k, numsSize-1);
    reverse(nums, 0, numsSize-1);
}

3. 示例说明

示例一

假设原数组nums为[1, 2, 3, 4, 5]，需要右移的步数为3，即k=3。

先将左边的[1, 2]和右边的[3, 4, 5]进行反转，得到[2, 1, 5, 4, 3]。

再将整个数组进行反转，得到[3, 4, 5, 1, 2]。

最终的结果就是经过循环右移3个位置的[3, 4, 5, 1, 2]。

示例二

假设原数组nums为[1, 2, 3, 4, 5, 6, 7]，需要右移的步数为7，即k=7。

因为k=n时，相当于没有移动，所以k=k%n。

在此例中，移动的步数为k=7%7=0，相当于没有移动，所以原数组中的元素顺序没有发生变化，结果为[1, 2, 3, 4, 5, 6, 7]。