拓冰网站定制 
题目分析LeetCode 189. 轮转数组给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。示例输入nums [1,2,3,4,5,6,7], k 3输出[5,6,7,1,2,3,4]输入nums [-1,-100,3,99], k 2输出[3,99,-1,-100]进阶要求 至少想出三种解法且能用空间复杂度 O(1) 的原地算法解决。核心思路这道题有四种经典解法从暴力到最优逐步递进关键预处理 无论哪种解法第一步都要 k k % n因为旋转 n 次等于没旋转避免无效计算。Java 实现方法一暴力循环移位O(n×k)会超时每次把最后一个元素取出整体后移一位重复 k 次。class Solution {public void rotate(int[] nums, int k) {int n nums.length;k k % n;for (int i 0; i k; i) {int last nums[n - 1];for (int j n - 1; j 0; j–) {nums[j] nums[j - 1];}nums[0] last;}}}缺点 时间复杂度 O(n×k)大数据量直接超时工程基本不用。方法二临时数组O(n) 时间O(n) 空间新建一个数组通过公式 newArr[(i k) % n] nums[i] 计算每个元素旋转后的位置最后拷贝回原数组。class Solution {public void rotate(int[] nums, int k) {int n nums.length;k k % n;int[] newArr new int[n];for (int i 0; i n; i) {newArr[(i k) % n] nums[i];}System.arraycopy(newArr, 0, nums, 0, n);}}关键点 System.arraycopy 是 Java 底层原生数组拷贝方法性能优于 for 循环赋值。方法三三次数组翻转O(n) 时间O(1) 空间面试标准答案核心原理 通过三次区间反转实现原地轮转。以 nums [1,2,3,4,5,6,7], k 3 为例步骤 操作 结果原始数组 — [1,2,3,4,5,6,7]Step 1 整体反转 [7,6,5,4,3,2,1]Step 2 反转前 k 个 [5,6,7,4,3,2,1]Step 3 反转剩余元素 [5,6,7,1,2,3,4] ✅class Solution {public void rotate(int[] nums, int k) {int n nums.length;k k % n;if (k 0) return;reverse(nums, 0, n - 1); // 整体反转 reverse(nums, 0, k - 1); // 反转前k个 reverse(nums, k, n - 1); // 反转剩余部分 } private void reverse(int[] nums, int left, int right) { while (left right) { int temp nums[left]; nums[left] nums[right]; nums[right] temp; left; right--; } }}复杂度 时间 O(n)每个元素最多被交换 2 次空间 O(1)纯原地操作。方法四环状替换O(n) 时间O(1) 空间数学原理 当数组长度 n 和旋转步数 k 的最大公约数为 g 时数组会被分成 g 个环每个环上的元素循环移动。class Solution {public void rotate(int[] nums, int k) {int n nums.length;k k % n;if (k 0) return;int count 0; // 已处理的元素个数 for (int start 0; count n; start) { int current start; int prev nums[start]; do { int next (current k) % n; int temp nums[next]; nums[next] prev; prev temp; current next; count; } while (start ! current); } }}执行过程nums [1,2,3,4,5,6], k 2环10→2→4→0处理元素 1,3,5环21→3→5→1处理元素 2,4,6GCD(6,2)2共 2 个环四种解法横向对比解法 时间复杂度 空间复杂度 适用场景暴力循环 O(n×k) O(1) 理解轮转逻辑不用于刷题临时数组 O(n) O(n) 快速过题三次翻转 O(n) O(1) 面试标准答案环状替换 O(n) O(1) 理论最优实现较复杂面试延伸如果面试官追问可以补充说明为什么三次翻转能 work 本质上是把数组分成 [0, n-k-1] 和 [n-k, n-1] 两段整体翻转后两段位置互换但内部逆序再分别翻转恢复内部顺序。向左轮转怎么办 向左 k 位等价于向右 n-k 位或者调整翻转顺序先翻前 k 个 → 再翻剩余 → 最后整体翻。reverse 函数能复用吗 能这是数组高频工具函数在反转字符串、验证回文串等题中都能复用。环状替换中为什么需要 GCD 如果 n 和 k 不互质从某个起点出发无法遍历所有元素必须从多个起点分别处理环的数量恰好等于 GCD(n, k)。这道题的三次翻转思想非常经典和旋转字符串、旋转链表属于同一类题型需要我顺带把这两道变形题的思路也整理一下吗 千问 LeetCode 189. 轮转数组 Java实现
题目分析LeetCode 189. 轮转数组给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。示例输入nums [1,2,3,4,5,6,7], k 3输出[5,6,7,1,2,3,4]输入nums [-1,-100,3,99], k 2输出[3,99,-1,-100]进阶要求 至少想出三种解法且能用空间复杂度 O(1) 的原地算法解决。核心思路这道题有四种经典解法从暴力到最优逐步递进关键预处理 无论哪种解法第一步都要 k k % n因为旋转 n 次等于没旋转避免无效计算。Java 实现方法一暴力循环移位O(n×k)会超时每次把最后一个元素取出整体后移一位重复 k 次。class Solution {public void rotate(int[] nums, int k) {int n nums.length;k k % n;for (int i 0; i k; i) {int last nums[n - 1];for (int j n - 1; j 0; j–) {nums[j] nums[j - 1];}nums[0] last;}}}缺点 时间复杂度 O(n×k)大数据量直接超时工程基本不用。方法二临时数组O(n) 时间O(n) 空间新建一个数组通过公式 newArr[(i k) % n] nums[i] 计算每个元素旋转后的位置最后拷贝回原数组。class Solution {public void rotate(int[] nums, int k) {int n nums.length;k k % n;int[] newArr new int[n];for (int i 0; i n; i) {newArr[(i k) % n] nums[i];}System.arraycopy(newArr, 0, nums, 0, n);}}关键点 System.arraycopy 是 Java 底层原生数组拷贝方法性能优于 for 循环赋值。方法三三次数组翻转O(n) 时间O(1) 空间面试标准答案核心原理 通过三次区间反转实现原地轮转。以 nums [1,2,3,4,5,6,7], k 3 为例步骤 操作 结果原始数组 — [1,2,3,4,5,6,7]Step 1 整体反转 [7,6,5,4,3,2,1]Step 2 反转前 k 个 [5,6,7,4,3,2,1]Step 3 反转剩余元素 [5,6,7,1,2,3,4] ✅class Solution {public void rotate(int[] nums, int k) {int n nums.length;k k % n;if (k 0) return;reverse(nums, 0, n - 1); // 整体反转 reverse(nums, 0, k - 1); // 反转前k个 reverse(nums, k, n - 1); // 反转剩余部分 } private void reverse(int[] nums, int left, int right) { while (left right) { int temp nums[left]; nums[left] nums[right]; nums[right] temp; left; right--; } }}复杂度 时间 O(n)每个元素最多被交换 2 次空间 O(1)纯原地操作。方法四环状替换O(n) 时间O(1) 空间数学原理 当数组长度 n 和旋转步数 k 的最大公约数为 g 时数组会被分成 g 个环每个环上的元素循环移动。class Solution {public void rotate(int[] nums, int k) {int n nums.length;k k % n;if (k 0) return;int count 0; // 已处理的元素个数 for (int start 0; count n; start) { int current start; int prev nums[start]; do { int next (current k) % n; int temp nums[next]; nums[next] prev; prev temp; current next; count; } while (start ! current); } }}执行过程nums [1,2,3,4,5,6], k 2环10→2→4→0处理元素 1,3,5环21→3→5→1处理元素 2,4,6GCD(6,2)2共 2 个环四种解法横向对比解法 时间复杂度 空间复杂度 适用场景暴力循环 O(n×k) O(1) 理解轮转逻辑不用于刷题临时数组 O(n) O(n) 快速过题三次翻转 O(n) O(1) 面试标准答案环状替换 O(n) O(1) 理论最优实现较复杂面试延伸如果面试官追问可以补充说明为什么三次翻转能 work 本质上是把数组分成 [0, n-k-1] 和 [n-k, n-1] 两段整体翻转后两段位置互换但内部逆序再分别翻转恢复内部顺序。向左轮转怎么办 向左 k 位等价于向右 n-k 位或者调整翻转顺序先翻前 k 个 → 再翻剩余 → 最后整体翻。reverse 函数能复用吗 能这是数组高频工具函数在反转字符串、验证回文串等题中都能复用。环状替换中为什么需要 GCD 如果 n 和 k 不互质从某个起点出发无法遍历所有元素必须从多个起点分别处理环的数量恰好等于 GCD(n, k)。这道题的三次翻转思想非常经典和旋转字符串、旋转链表属于同一类题型需要我顺带把这两道变形题的思路也整理一下吗