C语言实现LeetCode旋转数组的四种解法

暴力思路：三次翻转法

最直观的解题逻辑是通过倒序操作来实现位移。具体步骤分为三步：

1. 整体倒序：将整个数组反转。
2. 前半部分倒序：将前 k 个元素反转。
3. 后半部分倒序：将剩余元素反转。

这种方法不需要开辟新空间，完美符合时间复杂度 O(n) 和空间复杂度 O(1) 的要求。实现时，可利用双指针交换对应位置的数值。

C语言实现代码如下：

// 交换a，b位置
void exchange(int* a, int* b)
{
    int n = *a;
    *a = *b;
    *b = n;
}

// 对指定范围内元素进行翻转操作
void reverse(int* nums, int left, int right)
{
    while(left < right)
    {
        exchange(&nums[left], &nums[right]);
        left++;
        right--;
    }
}

void rotate(int* nums, int numsSize, int k){
    k %= numsSize; // 处理 k 大于数组长度的情况
    if(k == 0)
    {
        return; // 防止 k 为 0 导致无意义操作
    }
    reverse(nums, 0, numsSize - 1); // 全倒序
    reverse(nums, 0, k - 1);        // 前半部分倒序
    reverse(nums, k, numsSize - 1); // 后半部分倒序
}

外加数组法

如果追求代码的简洁性且允许额外的空间开销，可以创建一个临时数组。遍历原数组，将原数组下标为 n 的元素放入新数组的下标 (n + k) % numsSize 的位置。最后再将新数组内容拷贝回原数组。

该方法逻辑简单，不易出错，但空间复杂度为 O(n)。代码如下：

void rotate(int* nums, int numsSize, int k){
    int arr[numsSize] = {0};
    for(int n = 0; n < numsSize; n++)
    {
        // nums所有元素向前移动 k 个单位，依次存到数组arr
        arr[(k + n) % numsSize] = nums[n]; 
    }
    for(int n = 0; n < numsSize; n++)
    {
        nums[n] = arr[n];  // 将arr数组内容拷贝回原数组nums
    }
}

注：也可使用 malloc 动态开辟空间，原理相同，此处不再赘述。

格局抬高：利用 memcpy 优化

在有了“创建新数组”的思路后，我们可以进一步优化拷贝过程。标准库中的 memcpy() 函数用于复制内存块，忽略字符结束符 '\0'，可面向任何数据类型高效复制。

原型如下：

void * memcpy ( void * dest, const void * src, size_t num );

结合旋转数组的特性（末尾 k 个元素移到前面，其余元素后移），我们可以分三段进行内存拷贝，从而避免循环赋值，提高执行效率：

#include <string.h>

void rotate(int* nums, int numsSize, int k){
    int arr[numsSize];
    k %= numsSize;
    
    // 1. 将数组末尾的 k 个元素复制到新数组的前部
    memcpy(arr, nums + (numsSize - k), k * sizeof(int));
    
    // 2. 将数组剩余的 numsSize-k 个元素复制到新数组的后部
    memcpy(arr + k, nums, (numsSize - k) * sizeof(int));
    
    // 3. 将整理好的数据全部拷贝回原数组
    memcpy(nums, arr, numsSize * sizeof(int));
}

关于 memmove 的疑问

在处理重叠内存块时，memmove() 通常比 memcpy() 更安全，因为它能正确处理源区域和目标区域重叠的情况。然而，在上述代码中，我们使用了独立的临时数组 arr，源数据（原数组的部分切片）与目标数据（新数组）不存在内存重叠，因此使用 memcpy 是完全安全且性能更佳的。若直接在原数组上进行重叠区域的移位操作，则必须使用 memmove 以避免数据丢失。

环形替代法

这是LeetCode官方给出的一种高难度解法，核心在于数学推导。可以将数组想象成一个莫比乌斯环（参考下图示意）：

以步长 k 为间隔进行遍历，不断将当前元素的下一个目标位置元素取出并交换，直到回到原点。由于 gcd(k, numsSize) 决定了循环的次数，我们需要启动 gcd 次这样的“环形”操作，每次从一个未被访问的起始点开始，直到所有元素都被处理。

C语言实现需要借助最大公约数（GCD）函数来控制循环组数：

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
    int count = gcd(k, numsSize);
    
    for (int start = 0; start < count; ++start) {
        int current = start;
        int prev = nums[start];
        do {
            int next = (current + k) % numsSize;
            swap(&nums[next], &prev);
            current = next;
        } while (start != current);
    }
}

该方法实现了真正的原地操作（O(1) 空间）且只遍历数组一次，是性能与空间利用率最高的解法，但逻辑相对复杂，需要仔细梳理索引变化规律。

以上就是C语言解决LeetCode旋转数组问题的详细内容，更多关于C语言多方法超度旋转数组的资料请关注本站其它相关文章！