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

• 双指针翻转

• 环状替换