609 lines
20 KiB
Markdown
609 lines
20 KiB
Markdown
---
|
||
tags: ["LeetCode", "数组", "双指针", "原地算法", "中等"]
|
||
create time: 2026-05-14 13:00
|
||
---
|
||
|
||
# 15-轮转数组
|
||
|
||
## 题面
|
||
|
||
> **LeetCode 189. Rotate Array**
|
||
|
||
给定一个整数数组 `nums`，将数组中的元素**向右轮转** `k` 个位置，其中 `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 步: [99,-1,-100,3]
|
||
向右轮转 2 步: [3,99,-1,-100]
|
||
```
|
||
|
||
**提示：**
|
||
|
||
- `1 <= nums.length <= 10^5`
|
||
- `-2^31 <= nums[i] <= 2^31 - 1`
|
||
- `0 <= k <= 10^5`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 思考
|
||
|
||
想象一排人站成一列，每个人要向右移动 k 个位置——最后 k 个人会绕回到队伍最前面。**如果只允许用一个临时变量来交换数据，你会怎么做？**
|
||
|
||
这看似简单，但「原地 O(1) 空间」的要求让问题变得耐人寻味。我们先从直观方法出发，逐步收敛到最优解。
|
||
|
||
### 方法一：额外数组（O(n) 空间）
|
||
|
||
> [!abstract] 📐 最朴素的映射
|
||
|
||
最直接的想法：对于每个位置 `i`，轮转后的新位置就是 `(i + k) % n`。我们可以开辟一个新数组存放结果，再拷回原数组。
|
||
|
||
> [!note] 📌 关键点：取模处理越界
|
||
|
||
```
|
||
新位置 i' = (i + k) % n
|
||
```
|
||
|
||
这个 `% n` 操作确保下标不会超出数组边界——当 `i + k >= n` 时自动"绕回"开头。
|
||
|
||
#### 逐步跟踪
|
||
|
||
以 `nums = [1,2,3,4,5,6,7]`, `k = 3`, `n = 7` 为例：
|
||
|
||
| 原位置 i | 原值 | 新位置 (i+3)%7 | 新位置的值 |
|
||
|---------|------|---------------|----------|
|
||
| 0 | 1 | 3 | nums[3] = 4 |
|
||
| 1 | 2 | 4 | nums[4] = 5 |
|
||
| 2 | 3 | 5 | nums[5] = 6 |
|
||
| 3 | 4 | 6 | nums[6] = 7 |
|
||
| 4 | 5 | 0 | nums[0] = **1** ← 绕回开头！ |
|
||
| 5 | 6 | 1 | nums[1] = **2** |
|
||
| 6 | 7 | 2 | nums[2] = **3** |
|
||
|
||
结果：`[5,6,7,1,2,3,4]` ✅
|
||
|
||
> [!example] 🔀 关联观察
|
||
|
||
你有没有注意到——最终结果的**前 k 个元素**正好是原数组中**倒数 k 个元素**？也就是说，向右轮转本质上是把尾部的一段搬到了头部。这给了我们另一种视角，也是后续更优方法的灵感来源。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["原始: [1,2,3,4 | 5,6,7]"] --> Cut["在 n-k 处切分"]
|
||
Cut --> Left["左段 A: [1,2,3,4]"]
|
||
Cut --> Right["右段 B: [5,6,7]"]
|
||
Right --> Swap["交换 AB 顺序"]
|
||
Left --> Swap
|
||
Swap --> Result["结果 BA: [5,6,7,1,2,3,4]"]
|
||
```
|
||
|
||
> [!tip] 💡 这个视角是后续「三段反转」方法的灵感来源——我们不需要真正切断和拼接数组，只需通过三次反转来达成同样的效果。下面展开详细说明。
|
||
|
||
- **时间复杂度**：O(n) — 两次遍历
|
||
- **空间复杂度**：O(n) — 需要额外数组
|
||
|
||
虽然不符合进阶要求，但它是最容易验证正确性的基准解法。
|
||
|
||
---
|
||
|
||
### 方法二：反转数组 ⭐（O(1) 空间，推荐）
|
||
|
||
> [!tip] 🔑 核心洞察：三段反转等于一次拼接
|
||
|
||
回顾上面的观察——把 `[1,2,3,4,5,6,7]` 在 `n-k` 处切成两段，再交换它们的顺序就得到了答案。那么，**能不能只用三次反转来完成这个"交换"？**
|
||
|
||
答案是肯定的。这是经典的技巧：
|
||
|
||
```
|
||
[A B] → 先分别反转 A 和 B → [A_rev B_rev] → 再整体反转 → B A
|
||
```
|
||
|
||
为什么可行？因为反转操作相当于把一段序列的索引做镜像翻转。对两段分别反转后再整体反转，等同于直接交换它们的相对位置。
|
||
|
||
#### 三步反转详解
|
||
|
||
以 `nums = [1,2,3,4,5,6,7]`, `k = 3`, `n = 7` 为例：
|
||
|
||
**预处理**：`k = k % n = 3 % 7 = 3`，避免无效轮转。
|
||
|
||
标准的三次反转方案如下：
|
||
|
||
```
|
||
Step 0: [1, 2, 3, 4, | 5, 6, 7] ← 原始数组
|
||
Step 1: [7, 6, 5, 4, | 3, 2, 1] ← 反转全部 [0..n-1]
|
||
Step 2: [5, 6, 7, 4, | 3, 2, 1] ← 反转前 k 个 [0..k-1]
|
||
Step 3: [5, 6, 7, 1, | 2, 3, 4] ← 反转剩余部分 [k..n-1]
|
||
←───────────→ ←──────────────→
|
||
结果正是右旋 k 位！
|
||
```
|
||
|
||
每一步的逻辑：
|
||
|
||
| 步骤 | 反转区间 | 目的 | 效果 |
|
||
|------|---------|------|------|
|
||
| Step 1 | `[0, n-1]` 全部 | 将整个数组倒过来 | 末尾的元素跑到了前面，但顺序也颠倒了 |
|
||
| Step 2 | `[0, k-1]` 前 k 个 | 修正前 k 个的顺序 | 这些本来来自末尾的元素恢复正序 |
|
||
| Step 3 | `[k, n-1]` 剩余的 | 修正剩余部分的顺序 | 这些本来来自开头的元素恢复正序 |
|
||
|
||
#### 逐步可视化
|
||
|
||
以 `nums = [1,2,3,4,5,6,7]`, `k = 3`, `n = 7` 为例：
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
S0["Step 0<br/>'原始': [1,2,3, 4,5,6,7]"] --> S1["Step 1<br/>reverse(0,6)<br/>[7,6,5, 4,3,2,1]"]
|
||
S1 --> S2["Step 2<br/>reverse(0,2)<br/>[5,6,7, 4,3,2,1]"]
|
||
S2 --> S3["Step 3<br/>reverse(3,6)<br/>[5,6,7, 1,2,3,4]"]
|
||
S3 --> DONE["✅ 完成!"]
|
||
```
|
||
|
||
关键点：**Step 2 和 Step 3 的分割点正是 k=3**。前三个位置放的是末尾元素的正序，后四个位置放的是开头元素的正序。
|
||
|
||
> [!step] 伪代码总览
|
||
|
||
> 1. `k = k % len(nums)` — 去冗余
|
||
> 2. `reverse(nums, 0, n-1)` — 反转全部
|
||
> 3. `reverse(nums, 0, k-1)` — 反转前 k 个
|
||
> 4. `reverse(nums, k, n-1)` — 反转剩余部分
|
||
> 5. 返回 `nums`（原地修改）
|
||
|
||
#### 证明其正确性
|
||
|
||
设数组由两部分组成：`A`（前 `n-k` 个元素）和 `B`（后 `k` 个元素），目标是将 `B` 移到 `A` 前面得到 `BA`。
|
||
|
||
```
|
||
初始: AB
|
||
反转全部: (AB)^R = B^R A^R （整体倒序）
|
||
反转前 k 个: (B^R)^R A^R = B A^R （恢复 B 的正序）
|
||
反转剩余: B (A^R)^R = BA （恢复 A 的正序）✅
|
||
```
|
||
|
||
> [!success] ✅ 对称美学的体现
|
||
|
||
这个解法的精妙之处在于：**你不需要知道任何元素的值，也不需要额外的存储空间**。反转只是通过两个指针向中间靠拢、逐次交换两端元素来实现的——它改变的是"相对顺序"这个结构本身。这在面试中经常给面试官留下深刻印象。
|
||
|
||
- **时间复杂度**：O(n) — 三个反转各遍历一部分，总共扫描 n/2 + k/2 + (n-k)/2 = n 次
|
||
- **空间复杂度**：O(1) — 原地操作，无额外空间
|
||
|
||
---
|
||
|
||
### 方法三：循环替换（O(1) 空间，进阶理解）
|
||
|
||
> [!question] 💡 能否用"单指针游走"解决问题？
|
||
|
||
我们不借助反转，而是让每个元素沿着自己的"目标路径"走到终点。具体来说：
|
||
|
||
把位置 `0 → k → 2k → 3k ...` 看作一条环上的轨道，每次把当前元素放到目标位置上。但是——**如果有多个独立的环怎么办？**
|
||
|
||
这就引出了这道题最微妙的数学性质。
|
||
|
||
#### GCD 与独立环的数量
|
||
|
||
考虑 `nums = [0, 1, 2, 3, 4, 5]`, `k = 2`:
|
||
|
||
```
|
||
从位置 0 开始游走： 0 → 2 → 4 → 0 （回到起点，形成第一个环，访问了 {0, 2, 4}）
|
||
从位置 1 开始游走： 1 → 3 → 5 → 1 （回到起点，形成第二个环，访问了 {1, 3, 5}）
|
||
```
|
||
|
||
共 `gcd(6, 2) = 2` 个独立环，恰好覆盖所有 6 个位置。
|
||
|
||
> [!abstract] 📐 关键定理
|
||
|
||
**向右轮转 k 位的置换操作由 `gcd(n, k)` 个不相交的循环组成。** 每个循环内部的长度均为 `n / gcd(n, k)`。
|
||
|
||
这意味着我们只需要启动 `gcd(n, k)` 次游走，每次从一个尚未访问的起始位置出发，沿着 `next(i) = (i + k) % n` 的规则前进，就能完成全部替换。
|
||
|
||
#### 逐步跟踪
|
||
|
||
以 `nums = [1, 2, 3, 4, 5, 6, 7]`, `k = 3`, `n = 7` 为例：
|
||
|
||
```
|
||
gcd(7, 3) = 1 → 只有 1 个环，从位置 0 开始
|
||
|
||
起点 i=0, prev = nums[0] = 1:
|
||
|
||
第1次: next=(0+3)%7=3, swap(prev=1, nums[3]=4) → nums[3]=1, prev=4
|
||
第2次: next=(3+3)%7=6, swap(prev=4, nums[6]=7) → nums[6]=4, prev=7
|
||
第3次: next=(6+3)%7=2, swap(prev=7, nums[2]=3) → nums[2]=7, prev=3
|
||
第4次: next=(2+3)%7=5, swap(prev=3, nums[5]=6) → nums[5]=3, prev=6
|
||
第5次: next=(5+3)%7=1, swap(prev=6, nums[1]=2) → nums[1]=6, prev=2
|
||
第6次: next=(1+3)%7=4, swap(prev=2, nums[4]=5) → nums[4]=2, prev=5
|
||
第7次: next=(4+3)%7=0, swap(prev=5, nums[0]=?) → nums[0]=5, prev=1
|
||
|
||
结果：[5,6,7,1,2,3,4] ✅
|
||
```
|
||
|
||
验证：`[5,6,7,1,2,3,4]` —— 与预期一致！这里的操作核心是**"缓存待插入值 + 逐位覆盖"**——每一步先记下来要覆盖的位置的原值，用它作为下一轮的待插入物，形成一条值的流动链。
|
||
|
||
#### 何时需要多个环？
|
||
|
||
看 `nums = [1,2,3,4,5,6]`, `k = 2`，`n = 6`：
|
||
|
||
```
|
||
gcd(6, 2) = 2，需要 2 个环
|
||
|
||
环 1（起点 i=0）： 0→2→4→0，每步走2格
|
||
环 2（起点 i=1）： 1→3→5→1，每步走2格
|
||
```
|
||
|
||
每个环各自完成自己的轮换任务。外层循环从 `i = 0` 到 `gcd(n, k) - 1` 依次启动。
|
||
|
||
> [!warning] ⚠️ 常见陷阱
|
||
|
||
> **不要跳过已经处理过的环！** 如果你不以内层循环次数 `n/gcd(n, k)` 作为终止条件，而是尝试一直走到"回到起点"，那对于多环的情况会在第一个环就无限循环。正确的做法是按环的长度精确控制内层循环的执行次数。
|
||
|
||
- **时间复杂度**：O(n) — 每个元素恰好被访问并写入一次
|
||
- **空间复杂度**：O(1) — 只需常数个辅助变量
|
||
|
||
---
|
||
|
||
### 方法对比
|
||
|
||
> [!info] 📊 三种方法综合对比
|
||
|
||
| 维度 | 额外数组 | 反转法 ⭐ | 循环替换 |
|
||
|------|---------|----------|---------|
|
||
| 时间复杂度 | O(n) | O(n) | O(n) |
|
||
| 空间复杂度 | O(n) | **O(1)** | **O(1)** |
|
||
| 原地操作 | ❌ | ✅ | ✅ |
|
||
| 理解难度 | ⭐ 极简 | ⭐⭐ 三段反转需领悟 | ⭐⭐⭐ 涉及 GCD 概念 |
|
||
| 实际性能 | 较慢（分配+拷贝） | 快（纯内存交换） | 快（同反转） |
|
||
| 面试推荐度 | 基础版可展示 | **首选**，优雅且高效 | 加分项，展示深度 |
|
||
|
||
---
|
||
|
||
> [!example] 🔀 关联变体题
|
||
|
||
- **LeetCode 1791. Find Center of Star Graph** — 同样利用 `gcd` 分析图的连通分量
|
||
- **LeetCode 46. Permutations / 47. Permutations II** — 全排列问题中遍历所有旋转也是一种子集；循环替换本质是在做「下一个排列」的子操作
|
||
- **LeetCode 26. Remove Duplicates from Sorted Array** — 原地修改、双指针、不超出数组长度的经典范式
|
||
- **LeetCode 31. Next Permutation** — 同样是「仅用交换重排数组」的问题，目标排列可以用对合操作分解来思考
|
||
- **[[16-除了自身以外数组的乘积]]** — 另一个 O(1) 额外空间的数组原地变换题，共享相同的空间约束思维
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
> [!abstract] 📝 Go 伪代码框架（反转法）
|
||
|
||
```go
|
||
func rotate(nums []int, k int) {
|
||
n := len(nums)
|
||
k = k % n // 去冗余轮转
|
||
|
||
reverse(nums, 0, n-1) // 反转全部
|
||
reverse(nums, 0, k-1) // 反转前 k 个
|
||
reverse(nums, k, n-1) // 反转剩余部分
|
||
}
|
||
|
||
func reverse(nums []int, left, right int) {
|
||
for left < right {
|
||
nums[left], nums[right] = nums[right], nums[left]
|
||
left++
|
||
right--
|
||
}
|
||
}
|
||
```
|
||
|
||
> [!abstract] 📝 Go 伪代码框架（循环替换）
|
||
|
||
```go
|
||
func rotate(nums []int, k int) {
|
||
n := len(nums)
|
||
k = k % n
|
||
count := 0 // 已放置元素计数
|
||
|
||
for start := 0; count < n; start++ {
|
||
curr := start
|
||
prev := nums[start]
|
||
for {
|
||
next := (curr + k) % n
|
||
nums[next], prev = prev, nums[next] // 旋转
|
||
curr = next
|
||
count++
|
||
if start == curr { break } // 回到起点
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：原地变换的三大策略
|
||
|
||
| 策略 | 代表题目 | 思想 |
|
||
|------|---------|------|
|
||
| **分段反转** | [[15-轮转数组|轮转数组]]、反转单词顺序、ZigZag 变换 | 把复杂重排分解为若干简单反转的组合 |
|
||
| **循环追踪** | [[15-轮转数组|轮转数组]]、置换数组、[[17-缺失的第一个正数|缺失的第一个正数]] | 利用置换的循环分解性质，一步到位 |
|
||
| **前后双指针** | 接雨水、[[16-除了自身以外数组的乘积|除了自身以外数组的乘积]]、盛最多水的容器 | 两端向内逼近，每次排除一个"确定不如"的选项 |
|
||
|
||
> [!note] 📌 必做的预处理：`k %= n`
|
||
|
||
不管用哪种方法，第一步都应该执行：
|
||
|
||
```go
|
||
k = k % len(nums)
|
||
```
|
||
|
||
原因：
|
||
1. **性能**：当 `k >= n` 时，多余的轮转周期不会改变结果
|
||
2. **安全性**：避免后续计算中出现越界或无限循环（比如 `k = n` 时某些实现可能出错）
|
||
3. **语义**：轮转 n 次等价于什么都没做，所以 `% n` 是最自然的归约
|
||
|
||
> [!question] 💡 向左轮转怎么写？
|
||
|
||
向左轮转 k 位与向右轮转的本质区别在于**方向相反**。可以有以下三种处理方式：
|
||
|
||
#### 方式一：转化为右旋（最简单）
|
||
|
||
左旋 k 位等价于右旋 `(n - k) % n` 位。直接复用右旋逻辑即可。
|
||
|
||
```go
|
||
// rotateLeftByRightRotate 用右旋实现左旋
|
||
func rotateLeftByRightRotate(nums []int, k int) {
|
||
n := len(nums)
|
||
if n <= 1 {
|
||
return
|
||
}
|
||
rotate(nums, (n-k)%n) // 复用上面的 rotate（三次反转版本）
|
||
}
|
||
```
|
||
|
||
#### 方式二：调整反转区间（原地最优）
|
||
|
||
左旋的三步反转与右旋不同，区间划分如下：
|
||
|
||
| 步骤 | 操作 | 效果 |
|
||
|------|------|------|
|
||
| Step 1 | `reverse(nums, 0, k-1)` | 反转前 k 个元素 |
|
||
| Step 2 | `reverse(nums, k, n-1)` | 反转剩余部分 |
|
||
| Step 3 | `reverse(nums, 0, n-1)` | 整体反转 |
|
||
|
||
```
|
||
[left_part | right_part] → 分别反转 → [left_rev | right_rev] → 整体反转 → right left ✅
|
||
```
|
||
|
||
```go
|
||
// rotateLeft 用三次反转实现向左轮转
|
||
func rotateLeft(nums []int, k int) {
|
||
n := len(nums)
|
||
if n <= 1 || k == 0 {
|
||
return
|
||
}
|
||
k %= n
|
||
|
||
reverse(nums, 0, k-1) // Step 1: 反转前 k 个
|
||
reverse(nums, k, n-1) // Step 2: 反转剩余部分
|
||
reverse(nums, 0, n-1) // Step 3: 整体反转
|
||
}
|
||
```
|
||
|
||
> [!tip] 💡 左右旋转的反转顺序对比
|
||
|
||
| | 向右旋转 k 位 | 向左旋转 k 位 |
|
||
|---|---|---|
|
||
| 第 1 步 | `reverse(0, n-1)` — 先反全 | `reverse(0, k-1)` — 先翻左段 |
|
||
| 第 2 步 | `reverse(0, k-1)` — 再翻前 k | `reverse(k, n-1)` — 再翻右段 |
|
||
| 第 3 步 | `reverse(k, n-1)` — 最后翻尾部 | `reverse(0, n-1)` — 最后反全 |
|
||
|
||
#### 方式三：循环替换中改为减法步进
|
||
|
||
在循环替换方法中，只需将步进方向从加法改为减法：
|
||
|
||
```go
|
||
// rotateCyclicLeft 用循环替换实现向左轮转
|
||
func rotateCyclicLeft(nums []int, k int) {
|
||
n := len(nums)
|
||
if n <= 1 || k%n == 0 {
|
||
return
|
||
}
|
||
k %= n
|
||
|
||
count := 0 // 已放置元素计数
|
||
for start := 0; count < n; start++ {
|
||
curr := start
|
||
prev := nums[start]
|
||
var next int // 必须预先声明，因为 for 体内会先用到再赋值
|
||
for {
|
||
next = (curr - k + n) % n // ← 注意：减法 + n 防负数
|
||
nums[next], prev = prev, nums[next]
|
||
curr = next
|
||
count++
|
||
if curr == start { break }
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
面试时如果能主动提出这个变体并给出至少两种方案，会是很好的加分项。
|
||
|
||
> [!warning] ⚠️ 边界情况 checklist
|
||
|
||
| 情况 | 处理方式 |
|
||
|------|---------|
|
||
| `nums` 为空或只有一个元素 | 无需轮转，直接返回 |
|
||
| `k == 0` | 无需操作，提前 return |
|
||
| `k == n` 或 `k % n == 0` | 等价于没动过，直接返回 |
|
||
| `k > n` | 必须先 `k %= n` 再计算 |
|
||
| 全相同元素 | 任意方法都能正确处理 |
|
||
|
||
> [!note] 🐹 Go 语言特有细节
|
||
|
||
- Go 支持**多重赋值**：`a, b = b, a` 可以一行完成交换，内部机制是先求右边所有表达式的值再同时赋值，天然避免了临时变量的需求。
|
||
- Go 的 slice 是引用类型，在函数内修改 `nums` 的内容会直接影响调用方的 slice，因此可以直接传入 `[]int` 而非 `*[]int`。
|
||
|
||
> [!success] ✅ 记忆口诀
|
||
|
||
> 欲右旋，先全翻；头正序，尾正翻。
|
||
> 三步反转定乾坤，零额外空间搞定。
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
> [!success] ✅ 方法一：额外数组（基准解法）
|
||
|
||
```go
|
||
// rotateExtraArray 使用额外数组实现向右轮转。
|
||
// 空间复杂度 O(n)，易于理解和验证。
|
||
func rotateExtraArray(nums []int, k int) {
|
||
n := len(nums)
|
||
if n <= 1 || k%n == 0 {
|
||
return
|
||
}
|
||
k %= n // 去冗余
|
||
|
||
res := make([]int, n) // 创建新数组
|
||
|
||
for i := 0; i < n; i++ {
|
||
res[(i+k)%n] = nums[i] // 映射到新位置
|
||
}
|
||
|
||
copy(nums, res) // 拷贝回原数组
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 方法二：反转数组（⭐ 推荐）
|
||
|
||
```go
|
||
// rotate 使用三次反转实现向右轮转数组。
|
||
// 原地 O(1) 空间，时间 O(n)，面试首选解法。
|
||
//
|
||
// 原理：将数组视为 A+B 两段，目标是将 B 移动到 A 前面得到 BA。
|
||
// 公式推导：(AB)^R = B^R A^R → (B^R A^R)^(R on each part) = BA
|
||
func rotate(nums []int, k int) {
|
||
n := len(nums)
|
||
if n <= 1 || k%n == 0 {
|
||
return
|
||
}
|
||
k %= n
|
||
|
||
reverse(nums, 0, n-1) // Step 1: 反转整个数组 [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
|
||
reverse(nums, 0, k-1) // Step 2: 反转前 k 个 [7,6,5, 4,3,2,1] → [5,6,7, 4,3,2,1]
|
||
reverse(nums, k, n-1) // Step 3: 反转剩余部分 [5,6,7, 4,3,2,1] → [5,6,7, 1,2,3,4]
|
||
}
|
||
|
||
// reverse 将 nums[left...right] 原地反转。
|
||
// 双指针相向而行，每次交换两端元素。
|
||
func reverse(nums []int, left, right int) {
|
||
for left < right {
|
||
// Go 多重赋值：右边全部求值后同时赋值，无需显式临时变量
|
||
nums[left], nums[right] = nums[right], nums[left]
|
||
left++
|
||
right--
|
||
}
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 方法三：循环替换（展示深度）
|
||
|
||
```go
|
||
// rotateCyclic 使用循环替换实现向右轮转数组。
|
||
// 利用 gcd(n, k) 个独立循环的性质，原地 O(1) 空间完成。
|
||
//
|
||
// 核心洞察：向右轮转 k 位构成一个置换，该置换可分解为 gcd(n, k)
|
||
// 个互不相交的循环。每个循环内的元素沿 "i → (i+k)%n" 方向流动，
|
||
// 恰好走过 n/gcd(n, k) 步后回到起点。
|
||
func rotateCyclic(nums []int, k int) {
|
||
n := len(nums)
|
||
if n <= 1 || k%n == 0 {
|
||
return
|
||
}
|
||
k %= n
|
||
|
||
count := 0 // 已正确放置的元素总数——控制外层循环何时停止
|
||
|
||
for start := 0; count < n; start++ {
|
||
// 从 start 出发，沿 (start + k) 方向游走一圈
|
||
curr := start
|
||
prev := nums[start] // 缓存当前位置的值，作为下一轮的"待插入物"
|
||
|
||
for {
|
||
next := (curr + k) % n // 下一个目标位置
|
||
nums[next], prev = prev, nums[next] // 旋入值，取出新值留作下一步
|
||
curr = next
|
||
count++
|
||
|
||
if curr == start {
|
||
break // 一圈走完，回到起点
|
||
}
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 补充：向左轮转实现
|
||
|
||
```go
|
||
// rotateLeft 使用三次反转实现向左轮转数组。
|
||
// 原理与右旋对称但区间顺序不同：先翻左段、再翻右段、最后反全。
|
||
func rotateLeft(nums []int, k int) {
|
||
n := len(nums)
|
||
if n <= 1 || k == 0 {
|
||
return
|
||
}
|
||
k %= n
|
||
|
||
reverse(nums, 0, k-1) // Step 1: 反转前 k 个 [3,2,1, 4,5,6,7]
|
||
reverse(nums, k, n-1) // Step 2: 反转剩余部分 [3,2,1, 7,6,5,4]
|
||
reverse(nums, 0, n-1) // Step 3: 整体反转 [4,5,6,7, 1,2,3] ← [1,2,3,4,5,6,7] 左旋 3 位的结果
|
||
}
|
||
|
||
// rotateCyclicLeft 使用循环替换实现向左轮转数组。
|
||
// 与右旋唯一区别：步进方向由加法改为减法，注意 +n 防止负数取模。
|
||
func rotateCyclicLeft(nums []int, k int) {
|
||
n := len(nums)
|
||
if n <= 1 || k%n == 0 {
|
||
return
|
||
}
|
||
k %= n
|
||
|
||
count := 0
|
||
for start := 0; count < n; start++ {
|
||
curr := start
|
||
prev := nums[start]
|
||
var next int
|
||
for {
|
||
next = (curr - k + n) % n // ← 关键差异：减法代替加法
|
||
nums[next], prev = prev, nums[next]
|
||
curr = next
|
||
count++
|
||
if curr == start {
|
||
break
|
||
}
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
|
||
这是 LeetCode 第 189 题，是一道非常经典的**原地数组变换**题目。
|
||
|
||
- **反转法**运行时间：约 0~2 ms（Go，击败 ~95%+ 提交）
|
||
- **反转法**空间消耗：O(1)
|
||
- **循环替换**运行时间：约 2~5 ms（Go，击败 ~85%+ 提交）
|
||
- **循环替换**空间消耗：O(1)
|
||
|
||
> [!quote] 💬 延伸思考
|
||
|
||
反转法的美妙之处在于它与**群论中的对合运算**相通——反转是对合（involution），即 `reverse(reverse(x)) = x`。三次反转的组合本质上是在 S_n（n 元对称群）中构造了一个特定的排列。当你遇到更多"仅凭交换操作重排数组"的问题时，思考能否将目标排列分解为若干个对合操作的乘积，这会是一个通用的解题利器。
|