网站导航
> 技术文档 > 轮转数组或者旋转数组-力扣189

轮转数组或者旋转数组-力扣189

网友: 技术文档 2025-09-02 23:52:06

目录

题目

【算法1】完整的 C++ 代码，包含详细注释和变量声明说明：

算法说明

变量声明详解

核心原因：两种不同的区间约定

对比总结

结论

🔧 一、数组反转实现

1. ​整型数组反转（C++）​​

2. ​字符串反转（Python）​​

⚙️ 二、自定义范围反转

1. ​反转数组指定区间（左闭右闭）​​

2. ​反转字符串指定区间（左闭右开）​​

🌐 三、不同语言的实现差异

⚠️ 四、注意事项

💎 总结

2. ​额外数组法（直观易懂）​​

🔍 代码解析（额外数组法）

3. ​循环交换法（原地操作）​​

方法对比总结​

题目

给定一个整数数组 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 <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105 进阶：尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

【算法1】完整的 C++ 代码，包含详细注释和变量声明说明：

算法说明

这段代码实现了经典的\"三次反转\"数组旋转算法：

  1. ​整体反转​：先将整个数组反转

  2. ​部分反转​：然后反转前k个元素

  3. ​部分反转​：最后反转剩余元素

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，是一种高效的原位(in-place)算法。

变量声明详解

  • nums: vector&类型，整数向量的引用，表示需要被旋转的数组

  • k: int类型，表示向右旋转的步数

  • left: int类型，在reverse函数中表示反转操作的起始索引

  • right: int类型，在reverse函数中表示反转操作的结束索引

  • temp: int类型，在reverse函数中用作交换元素的临时变量

这种实现方式避免了使用额外空间，同时保证了算法的高效性。

class Solution {public: // 函数：rotate // 功能：将数组向右旋转k个位置 // 参数： // - nums: vector& 整数向量引用（需要被旋转的数组） // - k: int 旋转的步数（向右移动的位置数） void rotate(vector& nums, int k) { // 对k取模，防止k大于数组长度时出现无效旋转 // 例如：数组长度为5，k=7等同于k=2 (7 % 5 = 2) k = k % nums.size(); // 第一步：反转整个数组 // 例如：[1,2,3,4,5] -> [5,4,3,2,1] reverse(nums, 0, nums.size() - 1); // 第二步：反转前k个元素 // 例如：k=2时，反转前2个元素 [5,4] -> [4,5] reverse(nums, 0, k - 1); // 第三步：反转剩余元素（从索引k到末尾） // 例如：反转[3,2,1] -> [1,2,3] reverse(nums, k, nums.size() - 1); } // 函数：reverse // 功能：反转数组中从left到right索引范围内的元素 // 参数： // - nums: vector& 整数向量引用（需要被部分反转的数组） // - left: int 反转起始索引（包含） // - right: int 反转结束索引（包含） void reverse(vector& nums, int left, int right) { // 使用双指针法反转数组的指定区间 while (left < right) { // 临时变量temp: int 用于交换元素的临时存储 int temp = nums[left]; // 交换左右指针指向的元素 nums[left] = nums[right]; nums[right] = temp; // 移动指针：左指针向右移动，右指针向左移动 ++left; --right; } }};

疑惑：第二步：反转前k个元素reverse(nums, 0, k - 1); 为什么不是reverse(nums, 0, k ); reverse(nums.begin(), nums.end()); // 反转整个数组 reverse(nums.begin(), nums.begin() + k); // 反转前k个元素 不是说好的左开右闭吗

您提出了一个非常好的问题，这涉及到编程中一个核心且容易混淆的概念：​区间表示法。

您观察得非常仔细！您的疑问的核心在于：​图片中的自定义 reverse函数和 C++ 标准库的 std::reverse函数使用了不同的区间约定。

核心原因：两种不同的区间约定

  1. ​您的自定义 reverse函数（图片中）使用的是 [左闭右闭] 区间​

    • 函数签名：void reverse(vector& nums, int left, int right)

    • ​参数 left和 right都是包含的。这意味着要反转从索引 left到索引 right的所有元素。

    • 所以，要反转前 k个元素（即索引 0到索引 k-1），调用方式自然是 reverse(nums, 0, k - 1)。

  2. ​C++ 标准库 std::reverse使用的是 [左闭右开) 区间​

    • 函数签名：void reverse(It first, It last)

    • ​参数 first是起始迭代器（包含），last是终止迭代器（不包含）​。这意味着要反转从 first到 last-1的元素。

    • 所以，要反转前 k个元素（即从 begin()到 begin() + k - 1），调用方式就是 reverse(nums.begin(), nums.begin() + k)。因为 begin() + k指向的是第 k+1个元素的位置（即索引 k），这个位置本身不参与反转。

对比总结

特性

您的自定义 reverse函数

C++ 标准库 std::reverse函数

​区间约定​

​左闭右闭​ [left, right]

​左闭右开​ [first, last)

​反转前k个元素的调用​

reverse(nums, 0, k - 1)

reverse(nums.begin(), nums.begin() + k)

​参数含义​

right是最后一个元素的索引

last是最后一个元素之后的迭代器

​等效关系​

right≈ last - 1

last≈ right + 1

结论

所以，​这两行代码在逻辑上是完全等价的，只是它们所基于的“规则”不同：

  • reverse(nums, 0, k - 1)// 基于 [左闭右闭]规则，反转索引 0 到 k-1

  • reverse(nums.begin(), nums.begin() + k)// 基于 [左闭右开]规则，反转从开始到第k个元素之前的位置

​您的代码 reverse(nums, 0, k - 1)是正确的。它和您提到的标准库写法实现的是相同的功能，只是因为您自己实现的函数参数含义与标准库不同，所以调用方式看起来不同。

在编程时，最关键的是要始终明确你当前使用的函数或API遵循哪种区间约定，并相应地调整参数。您图片中的代码逻辑是清晰且正确的。

#include #include using namespace std;class Solution {public: void rotate(vector& nums, int k) { // 成员函数 int n = nums.size(); k %= n; if (k == 0) return; //三次反转实现旋转,将数组中的元素向右轮转k个位置即最右边K个元素放到了最左边 reverse(nums.begin(), nums.end()); // 反转整个数组 reverse(nums.begin(), nums.begin() + k); // 反转前k个元素 reverse(nums.begin() + k, nums.end()); // 反转剩余元素 }};

补充：

在编程中，“编辑”reverse函数通常指自定义实现反转功能（而非直接调用标准库）。以下是不同场景下的实现方法，涵盖数组、字符串及自定义范围反转：

🔧 一、数组反转实现

1. ​整型数组反转（C++）​​
void reverseArray(int arr[], int n) { int start = 0, end = n - 1; while (start < end) { swap(arr[start], arr[end]); // 交换首尾元素 start++; end--; }}

​说明​：双指针从两端向中间遍历，每次交换元素。时间复杂度 ​O(n)​。

2. ​字符串反转（Python）​​
def reverse_string(s: str) -> str: return s[::-1] # 切片操作直接反转

​说明​：Python切片 s[::-1]是最简洁的实现方式，时间复杂度 ​O(n)​。

⚙️ 二、自定义范围反转

1. ​反转数组指定区间（左闭右闭）​​
void customReverse(int arr[], int start, int end) { while (start < end) { swap(arr[start], arr[end]); start++; end--; }}

​调用示例​：

int arr[] = {1, 2, 3, 4, 5};customReverse(arr, 1, 3); // 反转索引 [1,3] → {1, 4, 3, 2, 5}

​关键​：需明确区间边界（含起始和结束位置）。

2. ​反转字符串指定区间（左闭右开）​​
#include void reverseSubstring(string& s, int start, int len) { reverse(s.begin() + start, s.begin() + start + len);}

​说明​：C++标准库 reverse使用迭代器，范围为 [first, last)（含头不含尾）。

🌐 三、不同语言的实现差异

​语言​

​数组/列表反转​

​字符串反转​

​C++​​

reverse(arr, arr + n)

reverse(s.begin(), s.end())

​Java​

Collections.reverse(Arrays.asList(arr))

new StringBuilder(s).reverse()

​Python

list.reverse()（原地）

s[::-1]（生成新字符串）

​JavaScript​

array.reverse()（原地）

s.split(\'\').reverse().join(\'\')

​注意​：

  • Java数组需转为 List再反转；

  • Python字符串不可变，切片返回新对象。

⚠️ 四、注意事项

  1. ​边界处理​

    • 确保索引不越界（如 start >= 0，end < 数组长度）。

    • 左闭右开区间：last指向末尾的下一个位置。

  2. ​性能优化​

    • 避免频繁内存分配（如JS/Python中拼接字符串改用列表）。

  3. ​特殊数据结构​

    • 链表反转需修改指针方向（见下方示例）：

      class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextdef reverseList(head: ListNode) -> ListNode: prev = None while head: next_node = head.next head.next = prev prev = head head = next_node return prev

💎 总结

编辑 reverse函数需关注：

  1. ​数据结构特性​（数组/字符串/链表）；

  2. ​语言内置支持​（如Python切片、C++标准库）；

  3. ​自定义需求​（如部分反转或原地操作）。

    根据场景选择合适实现，并严格处理边界条件即可高效完成反转功能。

2. ​额外数组法（直观易懂）​​

​原理​：用临时数组存储旋转后的结果，再复制回原数组。

void rotate(vector& nums, int k) { int n = nums.size(); k %= n; vector temp(n); // 计算新位置 for (int i = 0; i < n; i++) { temp[(i + k) % n] = nums[i]; // 映射到旋转后位置 [2,5,9] } nums = temp; // 复制回原数组}

以下是对旋转数组官方题解代码的解析，结合不同实现方案及优化思路：

🔍 代码解析（额外数组法）

void rotate(vector& nums, int k) { int n = nums.size(); vector newArr(n);  // 创建等长新数组 for (int i = 0; i < n; ++i) { newArr[(i + k) % n] = nums[i]; // 计算新位置并赋值 } nums.assign(newArr.begin(), newArr.end()); // 覆盖原数组}

​核心原理​：

通过 (i + k) % n直接映射旋转后位置，无需实际移动元素。

  • ​时间复杂度​：O(n)，遍历一次数组

  • ​空间复杂度​：O(n)，需额外存储新数组

3. ​循环交换法（原地操作）​​

​原理​：通过多次循环交换元素实现旋转，避免额外空间。

void rotate(vector& nums, int k) { int n = nums.size(); k %= n; // 循环 k 次，每次移动一个元素到正确位置 for (int start = 0, count = 0; count < n; start++) { int current = start; int prev = nums[start]; do { int next = (current + k) % n; swap(prev, nums[next]); // 交换元素并更新指针 [4](@ref) current = next; count++; } while (start != current); // 循环直到回到起点 }}

优势​：代码简洁，底层优化高效。

方法对比总结​

​方法​

​时间复杂度​

​空间复杂度​

​适用场景​

三次反转法

O(n)

O(1)

内存敏感场景（推荐）

额外数组法

O(n)

O(n)

可接受额外空间时

循环交换法

O(n)

O(1)

避免库依赖的原地操作

STL 实现

O(n)

O(1)

追求代码简洁性

网络标签：

相关问题