核心内容摘要
突破限制：Nucleus Co-Op让单PC变身多人游戏主机的全攻略
LeetCode
轮转数组 - 三次反转原地算法详解
问题理解问题描述给定一个整数数组nums将数组中的元素向右轮转k个位置其中k是非负数。
要求原地修改数组不使用额外的数组空间。
示例text输入: 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] 输入: nums [-1,-100,3,99], k 2 输出: [3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]要求原地修改不能使用额外的数组空间时间复杂度尽可能高效空间复杂度O(
1)
核心思路三次反转法为什么需要三次反转问题本质将数组后k个元素移动到前面直观思路可以先反转整个数组这样后k个元素就到了前面但顺序反了调整顺序再分别反转前k个元素和后n-k个元素恢复正确的顺序三次反转步骤反转整个数组将整个数组反转这样原数组的后k个元素就变成了前k个元素反转前 k 个元素恢复前k个元素的原始顺序反转后 n-k 个元素恢复后n-k个元素的原始顺序
代码逐行解析Java 解法javaclass Solution { public void rotate(int[] nums, int k) { int n nums.length; //
处理 k 大于数组长度的情况 k k % n; //
反转整个数组 reverse(nums, 0, n -
; //
反转前 k 个元素 reverse(nums, 0, k -
; //
反转后 n-k 个元素 reverse(nums, k, n -
; } // 辅助函数反转数组中指定范围的元素 private void reverse(int[] nums, int start, int end) { while (start end) { // 交换 start 和 end 位置的元素 int temp nums[start]; nums[start] nums[end]; nums[end] temp; // 移动指针 start; end--; } } }Python 解法pythonfrom typing import List class Solution: def rotate(self, nums: List[int], k: int) - None: Do not return anything, modify nums in-place instead. #
定义反转函数 def reverse(i: int, j: int) - None: 反转 nums 中从索引 i 到 j 的元素闭区间 while i j: # 交换元素 nums[i], nums[j] nums[j], nums[i] i 1 j - 1 n len(nums) #
处理 k 大于数组长度的情况 k % n # 轮转 k 次等于轮转 k % n 次 #
三次反转 reverse(0, n -
# 反转整个数组 reverse(0, k -
# 反转前 k 个元素 reverse(k, n -
# 反转后 n-k 个元素
Java 与 Python 语法对比
数组/列表操作操作JavaPython数组/列表长度nums.lengthlen(nums)交换元素需要临时变量a, b b, a取模运算k % nk % n函数定义private void reverse(...)def reverse(...) - None:
循环与控制流操作JavaPythonwhile 循环while (start end) { ... }while i j:指针移动start; end--;i 1; j - 1函数调用reverse(nums, 0, n-
reverse(0, n-
1)
原地修改操作JavaPython修改原数组直接修改数组元素直接修改列表元素空间复杂度O(
O(
1)
实例演示以nums [1,2,3,4,5,6,7],k 3为例演示三次反转过程初始状态text原始数组: [1, 2, 3, 4, 5, 6, 7] n 7, k 3步骤1反转整个数组text反转整个数组 (0 到
: [1,2,3,4,5,6,7] - [7,6,5,4,3,2,1]步骤2反转前 k 个元素 (0 到
text反转前3个元素 (0 到
: [7,6,5,4,3,2,1] - [5,6,7,4,3,2,1]步骤3反转后 n-k 个元素 (3 到
text反转后4个元素 (3 到
: [5,6,7,4,3,2,1] - [5,6,7,1,2,3,4]最终结果text[5,6,7,1,2,3,4]可视化过程text原始: [1, 2, 3, 4, 5, 6, 7] 反转全部: [7, 6, 5, 4, 3, 2, 1] 反转前3: [5, 6, 7, 4, 3, 2, 1] 反转后4: [5, 6, 7, 1, 2, 3, 4]
关键细节解析
为什么要对k取模当k n时旋转k次等价于旋转k % n次例如数组长度 7旋转 10 次等价于旋转 3 次避免不必要的重复旋转
为什么这种方法能工作数学证明设原数组为A目标数组为B其中B[i] A[(i - k) % n]三次反转的过程反转整个数组A[i] → A[n-1-i]反转前 k 个元素前 k 个元素恢复原始顺序反转后 n-k 个元素后 n-k 个元素恢复原始顺序直观理解将数组分为两部分[前 n-k 个元素]和[后 k 个元素]目标是[后 k 个元素] [前 n-k 个元素]通过三次反转实现这个目标
边界情况处理k 0不需要旋转直接返回k n旋转 n 次等于不旋转取模后为 0n 1只有一个元素无论 k 是多少数组不变k n取模后处理
为什么不能使用切片切片会创建新的数组/列表违反原地修改的要求空间复杂度变为 O(n)不符合题目要求
复杂度分析时间复杂度O(n)反转整个数组O(n)反转前 k 个元素O(k)反转后 n-k 个元素O(n-k)总时间复杂度O(n) O(k) O(n-k) O(n)空间复杂度O(
只使用了常数个额外变量原地修改没有使用额外数组空间
其他解法对比
暴力法逐个旋转pythondef rotate_brute_force(nums, k): n len(nums) k % n for _ in range(k): # 保存最后一个元素 last nums[-1] # 所有元素向右移动一位 for i in range(n-1, 0, -
: nums[i] nums[i-1] # 将最后一个元素放到开头 nums[0] last复杂度时间复杂度O(n × k)最坏情况下 O(n²)空间复杂度O(
1)
使用额外数组pythondef rotate_extra_array(nums, k): n len(nums) k % n # 创建新数组 rotated [0] * n for i in range(n): # 计算新位置 new_index (i k) % n rotated[new_index] nums[i] # 将结果复制回原数组 for i in range(n): nums[i] rotated[i]复杂度时间复杂度O(n)空间复杂度O(n)不符合原地修改要求
环状替换法pythondef rotate_cyclic(nums, k): n len(nums) k % n # 计算需要处理的环的数量 count 0 start 0 while count n: current start prev nums[start] while True: # 计算下一个位置 next_index (current k) % n # 保存下一个位置的元素 temp nums[next_index] # 将前一个元素放到当前位置 nums[next_index] prev # 更新变量 prev temp current next_index count 1 # 如果回到起点结束当前环 if start current: break start 1复杂度时间复杂度O(n)空间复杂度O(
缺点逻辑复杂容易出错
九、
常见问题与解答Q1: 如果 k 是负数怎么办A1: 题目说明 k 是非负数所以不需要处理负数情况。
但如果需要处理可以将负数转换为正数k k % n nQ2: 为什么不能直接使用切片A2: 切片会创建新的列表违反原地修改的要求。
题目明确要求 Do not return anything, modify nums in-place instead.Q3: 这个算法适用于所有情况吗A3: 是的算法适用于所有情况包括空数组n0不会执行任何操作单个元素n1不会改变k0不会改变kn取模后处理Q4: 这个算法容易理解吗A4: 三次反转算法需要一些思考才能理解但一旦理解就很容易记忆。
它是解决旋转数组问题的经典算法。
Q5: 有没有更直观的解法A5: 环状替换法更直观直接按照旋转的数学定义移动元素但实现更复杂。
三次反转法实现简单且高效。
相关题目
LeetCode
旋转链表pythondef rotateRight(head, k): if not head or not head.next or k 0: return head # 计算链表长度 length 1 tail head while tail.next: tail tail.next length 1 # 处理 k k % length if k 0: return head # 找到新的尾节点 new_tail head for _ in range(length - k -
: new_tail new_tail.next # 重新连接链表 new_head new_tail.next new_tail.next None tail.next head return new_head
LeetCode
旋转函数pythondef maxRotateFunction(nums): n len(nums) total_sum sum(nums) # 计算 F(
f0 0 for i in range(n): f0 i * nums[i] max_val f0 current f0 # 计算 F(
到 F(n-
for k in range(1, n): # F(k) F(k-
sum(nums) - n * nums[n-k] current current total_sum - n * nums[n - k] max_val max(max_val, current) return max_val
LeetCode
反转字符串中的单词pythondef reverseWords(s): # 移除多余空格 words s.split() # 反转单词顺序 words.reverse() # 用空格连接单词 return .join(words)
十一、
总结核心要点三次反转是关键通过三次反转实现数组的原地旋转取模操作很重要处理 k 大于数组长度的情况原地修改要求不能使用额外数组空间算法步骤计算k k % n处理 k 大于数组长度的情况反转整个数组反转前 k 个元素反转后 n-k 个元素时间复杂度与空间复杂度时间复杂度O(n)每个元素被访问两次反转时空间复杂度O(
只使用常数个额外变量适用场景需要原地修改数组需要高效旋转数组元素不允许使用额外数组空间扩展思考这个算法展示了如何通过简单的操作反转实现复杂的变化旋转。
类似的思想可以应用到其他问题中如字符串旋转链表旋转矩阵旋转掌握三次反转算法不仅能够解决轮转数组问题还能够理解原地操作和数组操作的核心技巧是面试中非常重要的算法技能。