LeetCode 189. 轮转数组（C语言详解｜三种解法 + 图解）

一、题目描述

给定一个整数数组 nums，将数组中的元素 向右轮转 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️⃣ 使用额外数组
2️⃣ 环状替换（Cycle Replacement）
3️⃣ 数组翻转（最经典）

三、解法一：额外数组

思路

将元素直接放到 旋转后的正确位置

元素 nums[i] 的新位置是：

(i + k) % n

示例：

nums = [1,2,3,4,5,6,7]
k = 3
n = 7

位置变化：

0 → 3
1 → 4
2 → 5
3 → 6
4 → 0
5 → 1
6 → 2

C语言代码

void rotate(int* nums, int numsSize, int k) {
int* temp = (int*)malloc(sizeof(int) * numsSize);

k = k % numsSize;

for(int i = 0; i < numsSize; i++)
{
temp[(i + k) % numsSize] = nums[i];
}

for(int i = 0; i < numsSize; i++)
{
nums[i] = temp[i];
}

free(temp);
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

缺点：需要额外数组。

四、解法二：环状替换（Cycle Replacement）

思路

数组旋转其实会形成 若干个循环。

例如：

nums = [1,2,3,4,5,6,7]
k = 3

移动路径：

0 → 3 → 6 → 2 → 5 → 1 → 4 → 0

每次把元素放到 (current + k) % n 的位置。

需要记录移动次数 count，直到所有元素移动完成。

C语言代码

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

for(int start = 0; count < numsSize; start++)
{
int current = start;
int prev = nums[start];

do
{
int next = (current + k) % numsSize;

int temp = nums[next];
nums[next] = prev;
prev = temp;

current = next;
count++;

} while(current != start);
}
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

优点：

• 不需要额外空间

缺点：

• 逻辑稍复杂

五、解法三：数组翻转（最经典）

这是 面试最推荐的方法 ⭐⭐⭐⭐

核心思想：

通过 三次翻转 实现数组旋转。

举例

nums = [1,2,3,4,5,6,7]
k = 3

第一步：整体翻转

7 6 5 4 3 2 1

第二步：翻转前 k 个

5 6 7 4 3 2 1

第三步：翻转后 n-k 个

5 6 7 1 2 3 4

C语言代码

void reverse(int* nums, int left, int right)
{
while(left < right)
{
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;

left++;
right–;
}
}

void rotate(int* nums, int numsSize, int k) {

k = k % numsSize;

reverse(nums, 0, numsSize – 1);
reverse(nums, 0, k – 1);
reverse(nums, k, numsSize – 1);
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

优点：

• 原地修改

• 实现简单

• 面试最常见

六、三种方法总结

面试回答顺序建议：

先说：额外数组
再说：翻转法（最佳）
最后补充：环状替换

✅ 核心知识点

• 数组旋转

• 模运算 (i + k) % n

• 双指针翻转

• 环状替换