1. 题目描述(题目链接)给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。示例输入: nums [1,2,3,4,5,6,7], k 3输出: [5,6,7,1,2,3,4]2. 方法一辅助数组法核心思想是开辟一个新的数组将原数组中的每个元素直接放到它最终应该在的位置上。核心公式推导对于原数组下标为 i 的元素向右轮转 k 位后它的新下标 new_index 为new_index (i k) % n 其中 n 为数组长度class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); vectorint nums2(n); // 将每个元素直接放到最终位置 for (int i 0; i n; i) { nums2[(i k) % n] nums[i]; } // 将新数组拷贝回原数组 nums nums2; } };复杂度分析时间复杂度 O(N)遍历一次数组。空间复杂度 O(N)需要创建一个与原数组等大的新数组。3. 方法二三次翻转法最优解这是本题在面试中最受青睐的解法。核心思路向右轮转 k 位本质上就是将数组的后 k 个元素移动到前面。我们可以通过以下三步实现整体翻转将整个数组翻转。此时原本在末尾的 k 个元素跑到了数组的最前面翻转前 k 个元素将这 k 个元素恢复顺序。翻转剩余的 n-k 个元素将剩余元素恢复顺序。演示假设 nums [1,2,3,4,5,6,7], k 3整体翻转 [1,2,3,4,5,6,7] - [7,6,5,4,3,2,1]翻转前 k 个 (前3个) [7,6,5] - [5,6,7]。数组变为[5,6,7,4,3,2,1]翻转剩余部分 (后4个) [4,3,2,1] - [1,2,3,4]。数组变为[5,6,7,1,2,3,4] (完成)注意 如果 k 大于数组长度需要先进行 k k % n 取余操作因为轮转 n 次等于没轮转。代码实现 (C)class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); k k % n; // 处理 k n 的情况 // 使用 C STL 的 reverse 函数 reverse(nums.begin(), nums.end()); // 1. 整体翻转 reverse(nums.begin(), nums.begin() k); // 2. 翻转前 k 个 reverse(nums.begin() k, nums.end()); // 3. 翻转剩余部分 } };复杂度分析时间复杂度ON每个元素被翻转了两次。空间复杂度O1原地修改不需要额外空间。4. 方法三环形替换法原地算法这也是一种O(1)空间的原地算法但逻辑比三次翻转法更复杂。核心思路我们可以直接把每个元素放到它最终的位置上。如果我们从下标 0 开始将 nums[0] 移动到 (0k)%n然后继续移动被覆盖的元素我们会形成一个闭环。但是如果 n 和 k 的最大公约数大于 1我们会在回到起点时还有元素没有移动。因此我们需要从下一个下标开始继续这个过程直到所有元素都被移动。代码实现class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); k k % n; int count 0; // 记录已移动的元素个数 // 当已移动元素数小于 n 时继续 for (int start 0; count n; start) { int current start; int prev nums[start]; do { // 计算下一个位置 int next (current k) % n; // 暂存下一个位置的值并将 prev 放入 swap(nums[next], prev); // 移动到下一个位置 current next; count; } while (start ! current); // 形成闭环后退出 } } };复杂度分析时间复杂度 O(N)每个元素只被访问和移动一次。空间复杂度 O(1)。5. 总结算法名称时间复杂度空间复杂度辅助数组法O(N)O(N)三次翻转法O(N)O(1)环形替换法O(N)O(1)
1. 题目描述(题目链接)给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。示例输入: nums [1,2,3,4,5,6,7], k 3输出: [5,6,7,1,2,3,4]2. 方法一辅助数组法核心思想是开辟一个新的数组将原数组中的每个元素直接放到它最终应该在的位置上。核心公式推导对于原数组下标为 i 的元素向右轮转 k 位后它的新下标 new_index 为new_index (i k) % n 其中 n 为数组长度class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); vectorint nums2(n); // 将每个元素直接放到最终位置 for (int i 0; i n; i) { nums2[(i k) % n] nums[i]; } // 将新数组拷贝回原数组 nums nums2; } };复杂度分析时间复杂度 O(N)遍历一次数组。空间复杂度 O(N)需要创建一个与原数组等大的新数组。3. 方法二三次翻转法最优解这是本题在面试中最受青睐的解法。核心思路向右轮转 k 位本质上就是将数组的后 k 个元素移动到前面。我们可以通过以下三步实现整体翻转将整个数组翻转。此时原本在末尾的 k 个元素跑到了数组的最前面翻转前 k 个元素将这 k 个元素恢复顺序。翻转剩余的 n-k 个元素将剩余元素恢复顺序。演示假设 nums [1,2,3,4,5,6,7], k 3整体翻转 [1,2,3,4,5,6,7] - [7,6,5,4,3,2,1]翻转前 k 个 (前3个) [7,6,5] - [5,6,7]。数组变为[5,6,7,4,3,2,1]翻转剩余部分 (后4个) [4,3,2,1] - [1,2,3,4]。数组变为[5,6,7,1,2,3,4] (完成)注意 如果 k 大于数组长度需要先进行 k k % n 取余操作因为轮转 n 次等于没轮转。代码实现 (C)class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); k k % n; // 处理 k n 的情况 // 使用 C STL 的 reverse 函数 reverse(nums.begin(), nums.end()); // 1. 整体翻转 reverse(nums.begin(), nums.begin() k); // 2. 翻转前 k 个 reverse(nums.begin() k, nums.end()); // 3. 翻转剩余部分 } };复杂度分析时间复杂度ON每个元素被翻转了两次。空间复杂度O1原地修改不需要额外空间。4. 方法三环形替换法原地算法这也是一种O(1)空间的原地算法但逻辑比三次翻转法更复杂。核心思路我们可以直接把每个元素放到它最终的位置上。如果我们从下标 0 开始将 nums[0] 移动到 (0k)%n然后继续移动被覆盖的元素我们会形成一个闭环。但是如果 n 和 k 的最大公约数大于 1我们会在回到起点时还有元素没有移动。因此我们需要从下一个下标开始继续这个过程直到所有元素都被移动。代码实现class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); k k % n; int count 0; // 记录已移动的元素个数 // 当已移动元素数小于 n 时继续 for (int start 0; count n; start) { int current start; int prev nums[start]; do { // 计算下一个位置 int next (current k) % n; // 暂存下一个位置的值并将 prev 放入 swap(nums[next], prev); // 移动到下一个位置 current next; count; } while (start ! current); // 形成闭环后退出 } } };复杂度分析时间复杂度 O(N)每个元素只被访问和移动一次。空间复杂度 O(1)。5. 总结算法名称时间复杂度空间复杂度辅助数组法O(N)O(N)三次翻转法O(N)O(1)环形替换法O(N)O(1)
