C语言原地轮转数组：三次逆转法实战

题目背景与目标

给定一个整数数组 nums，要求将其中的元素向右轮转 k 个位置。例如输入 [1,2,3,4,5,6,7] 且 k=3，输出应为 [5,6,7,1,2,3,4]。

核心挑战在于限制额外空间使用（空间复杂度需为 O(1)），即必须在原数组上直接修改数据，不能分配新数组来存储结果。同时需要正确处理 k 值超过数组长度的异常情况。

核心策略：三次逆转法

利用数组翻转的特性，可以通过三步反转完成轮转：

1. 整体逆转：将数组完全倒序。
2. 前半段逆转：将前 k 个元素再次倒序，恢复其在轮转后的正确顺序。
3. 后半段逆转：将剩余元素再次倒序，恢复其正确顺序。

以实例 nums=[1,2,3,4,5,6,7], k=3 为例演示：

• 原始：[1, 2, 3, 4, 5, 6, 7]
• 第1步（整体逆转）：[7, 6, 5, 4, 3, 2, 1]
• 第2步（逆转前k个 [0, k-1]）：[5, 6, 7, 4, 3, 2, 1]
• 第3步（逆转后部 [k, n-1]）：[5, 6, 7, 1, 2, 3, 4]（达成目标）

第一步：整体逆转

设置两个指针，begin 指向数组起始位置，end 指向末尾。不断交换两指针所指的值，并向中间移动，直到相遇。

第二步：逆转子数组 [0, k - 1]

复用相同的交换逻辑，但这次仅针对索引从 0 到 k-1 的范围进行操作。

第三步：逆转子数组 [k, numsSize - 1]

最后对剩余的尾部区域进行同样的逆转操作，即可完成全部元素的重新排列。

至此，通过两次局部逆转，原本被大翻转过来的后缀部分也回到了应有的逻辑位置。

关键细节：处理 k 越界

如果轮转次数 k 大于数组长度 n，直接按 k 取值会导致访问越界或逻辑错误。根据模运算特性，数组向右轮转 k 次等同于向右轮转 k % n 次。例如长度为 7 的数组，右旋 10 次等同于右旋 3 次（10 % 7 = 3）。

因此在开始计算前，必须先执行取余操作：

if (k > numsSize)
    k %= numsSize;

C语言完整实现

以下为包含主函数的完整示例代码。由于 LeetCode 等平台仅需实现接口函数，但在本地调试时需要主函数打印结果。代码中封装了 rotate1 函数用于复用指针交换逻辑。

#include <stdio.h>

// 辅助函数：逆转指定范围的数组
void rotate1(int* begin, int* end)
{
	while (begin < end)
	{
		int t = *begin;
		*begin = *end;
		*end = t;
		++begin;
		--end;
	}
}

// 主轮转函数
void rotate(int* nums, int numsSize, int k) 
{
	// 1. 处理 k 越界情况
	if (k > numsSize)
	{
		k %= numsSize;
	}
	// 2. 准备指针
	int* begin = nums;
	int* end = nums + numsSize - 1;

	// 3. 第一次逆转：整体
	rotate1(begin, end);
	// 4. 第二次逆转：前 k 个
	rotate1(begin, begin + k - 1);
	// 5. 第三次逆转：剩余部分
	rotate1(begin + k, end);
}

int main()
{
	int nums[] = { 1,2,3,4,5,6,7 };
	int sz = sizeof(nums) / sizeof(nums[0]);
	
	// 执行轮转
	rotate(nums, sz, 3);

	// 打印结果验证
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", nums[i]);
	}
	return 0;
}

以上就是C语言原地轮转数组三次逆转法的详细内容，更多关于C语言数组算法优化的资料请关注本站其它相关文章！