【小白笔记】移除元素与删除有序数组中的重复项与轮转数组（三步反转）

虽然题目要求是“移除元素”，但数组的物理特性决定了我们不能像链表那样通过改变指针就“切掉”一个节点。在数组中，删除一个元素通常意味着要将后面所有的元素向前挪动。

为了达到O(N)O(N)O(N)的高效处理，我们再次祭出**“双指针”**大法。

1. 核心思路：快慢指针（数据搬运法）

我们将数组想象成一个“工地”，有两个人在干活：

• 快指针 (fast)：负责寻找“有用的物资”（即不等于val的元素）。
• 慢指针 (slow)：负责接收物资，并按顺序堆放在数组的前面。

具体步骤：

1. fast指针从头到尾遍历数组。
2. 如果nums[fast] != val：说明找到了一个需要保留的元素。
3. 我们就把这个元素赋值给slow所在的位置：nums[slow] = nums[fast]。
4. 然后slow向后移动一位，准备接收下一个。

2. 代码实现 (Python)

classSolution:defremoveElement(self,nums:List[int],val:int)->int:# slow 指针表示：下一个要存放“非 val 元素”的位置slow=0# fast 指针遍历整个数组forfastinrange(len(nums)):# 如果当前元素不是我们要剔除的 valifnums[fast]!=val:# 把它搬运到 slow 所在的位置nums[slow]=nums[fast]# slow 往前走一步slow+=1# 最后 slow 的数值刚好就是新数组的长度 kreturnslow

3. 为什么这个方法有效？

• 原地操作：我们没有创建新数组，而是在原数组上进行覆盖。
• 逻辑保证：由于fast总是跑在slow前面（或相等），所以我们搬运数据时，永远不会覆盖掉fast还没检查到的数据。
• 结果返回：当循环结束时，slow之前的所有位置都填好了合格的元素，其索引值恰好等于元素的个数。

4. 延伸思考：如果 val 很少怎么办？

上面的方法在val很多时非常高效。但如果数组很大（如 100 万个元素），而val只有一个，上面的代码依然会把剩下的 99 万个元素全部搬运一遍。

这时候我们可以使用“双指针——对撞指针”优化：

1. 左指针left从头找等于val的。
2. 右指针right从尾找不等于val的。
3. 直接把右边的“好元素”覆盖到左边的“坑”里。
   这样可以减少大量的元素搬运操作。

5. 复杂度分析

• 时间复杂度：O(N)O(N)O(N)。只需遍历一次数组。
• 空间复杂度：O(1)O(1)O(1)。只用了两个整数变量。

对比总结：

• 链表题目：难点在于指针的交换顺序（怕断了）和边界处理（dummy）。
• 数组题目：难点在于如何在不搬运大量数据的情况下，“原地”完成任务。

这个问题是第 27 题（移除元素）的延伸。在第 27 题中我们是寻找不等于val的值，而在这道题中，我们要寻找的是**“不重复”**的值。

由于数组是**有序（非严格递增）**的，相同的元素一定会挤在一起。这意味着：只要一个元素和它左边的元素不同，它就是一个“新出现的”唯一元素。

1. 核心思路：快慢指针（去重版）

我们同样使用两个指针：

• 慢指针 (slow)：指向当前已确定的唯一元素序列的最后一个位置。
• 快指针 (fast)：从第二个元素开始扫描整个数组。

逻辑规则：

1. 如果nums[fast]不等于nums[slow]：说明我们发现了一个新的唯一数字。
2. 我们需要把slow向后移一位，然后把这个新数字搬运过去：nums[slow] = nums[fast]。
3. 如果相等，说明是重复项，fast继续往后找，slow原地待命。

2. 代码实现 (Python)

classSolution:defremoveDuplicates(self,nums:List[int])->int:ifnotnums:return0# slow 指向当前唯一元素序列的末尾slow=0# fast 从 1 开始遍历，因为第一个元素（index 0）必然是唯一的forfastinrange(1,len(nums)):# 如果快指针发现了一个与当前 slow 不同的新元素ifnums[fast]!=nums[slow]:# slow 往前挪一个坑位slow+=1# 把新元素填进去nums[slow]=nums[fast]# 返回长度 k。因为索引是从 0 开始的，所以长度是索引 + 1returnslow+1

3. 图解模拟

假设nums = [1, 1, 2]：

1. 初始：slow = 0,nums[slow] = 1。fast从索引1开始。
2. 第一步：nums[fast]是1。nums[1] == nums[0]，重复了！fast继续。
3. 第二步：nums[fast]是2。nums[2] != nums[0]，新元素出现！
   • slow变成1。
   • nums[1] = nums[2]（即把2搬到索引1）。
   • 此时数组前两个元素为[1, 2]。
4. 结束：返回slow + 1 = 2。

4. 复杂度分析

• 时间复杂度：O(N)O(N)O(N)，其中NNN是数组长度。
• 空间复杂度：O(1)O(1)O(1)，原地修改，只用了两个指针变量。

“向右轮转”（Right Rotation）可以想象成一组人手拉手围成一个圈，然后大家集体顺时针挪动位置。

对于数组来说，每一个元素都往右边移动kkk个位置，而最右边的元素因为“撞到了墙”，会绕回到数组的最左边。

1. 动态演示

假设数组为[1, 2, 3, 4, 5]，我们向右轮转k=1k = 1k=1次：

1. 最后一位5挪出来，准备去“超车”。
2. 前四位[1, 2, 3, 4]集体向右平移一格，变成[_, 1, 2, 3, 4]。
3. 挪出的5填补到最左边的空位。

• 结果：[5, 1, 2, 3, 4]

2. 多步轮转的规律

如果向右轮转k=2k = 2k=2次（以[1, 2, 3, 4, 5]为例）：

• 第 1 次轮转：[5, 1, 2, 3, 4]
• 第 2 次轮转：[4, 5, 1, 2, 3]

你会发现一个有趣的现象：末尾的kkk个元素跑到了数组的最前面，而剩下的元素原封不动地向后瞬移了。

4. 为什么要强调kk %= nk？

如果你有 7 个元素，向右轮转 7 次，数组会变回原样。
所以：

• 轮转8次===轮转1次。
• 轮转100次===轮转100÷7100 \div 7100÷7的余数次。

这就是为什么在写代码时，第一步通常是k = k % len(nums)，这样可以避免做无用功，也能防止kkk太大导致索引出错。

这种“切开重排”的思路虽然直观，但在计算机内存里，直接“搬动”一整块数据往往需要额外的空间。三步反转法的高明之处就在于：它不使用额外空间，只靠原地翻转就达到了“搬动”的效果。

一种极其优雅且经典的算法：三步反转法。

1. 核心思路：三步反转法

假设数组为[1, 2, 3, 4, 5, 6, 7]，我们要向右轮转k = 3个位置。
轮转后的目标结果应该是：[5, 6, 7, 1, 2, 3, 4]。

观察这个结果，你会发现它可以通过以下三次反转得到：

1. 反转整个数组：
   [7, 6, 5, 4, 3, 2, 1]
2. 反转前 k 个元素（即前 3 个）：
   [5, 6, 7, 4, 3, 2, 1]
3. 反转剩余的元素（即后 4 个）：
   [5, 6, 7, 1, 2, 3, 4]——成功！

2. 代码实现 (Python)

classSolution:defrotate(self,nums:List[int],k:int)->None:""" Do not return anything, modify nums in-place instead. """n=len(nums)# 1. 预处理 k：如果 k 大于数组长度，取余数# 比如长度为 7，轮转 8 次等于轮转 1 次k%=n# 定义一个辅助函数：反转数组的指定区间defreverse(l:int,r:int):whilel<r:nums[l],nums[r]=nums[r],nums[l]l+=1r-=1# 2. 执行三步反转reverse(0,n-1)# 全局反转reverse(0,k-1)# 反转前半部分reverse(k,n-1)# 反转后半部分

4. 复杂度分析

• 时间复杂度：O(N)O(N)O(N)。虽然我们反转了三次，但总的遍历次数依然是线性的（第一次全量，后两次加起来也是全量，总共相当于遍历了两遍数组）。
• 空间复杂度：O(1)O(1)O(1)。我们只使用了常数个额外变量，所有的交换都在原数组上完成。

5. 这种方法的妙处

你可能会问：“我是怎么想到要反转的？”
其实这是一种对称性的利用。轮转操作实际上是将数组切成两部分A和B（A=[1,2,3,4],B=[5,6,7]A = [1,2,3,4], B = [5,6,7]A=[1,2,3,4],B=[5,6,7]），然后把它们交换位置变成BA。

• 反转整个数组得到(AB)T=BTAT(AB)^T = B^T A^T(AB)T=BTAT。
• 再分别反转局部得到(BT)T(AT)T=BA(B^T)^T (A^T)^T = BA(BT)T(AT)T=BA。

这种“整体反转+局部反转”的技巧在处理字符串旋转、翻转单词顺序等题目时非常通用。

在 Python（以及大多数编程语言）中，%=是取模赋值运算符。

k %= n实际上是k = k % n的简写。它的作用是：计算k除以n的余数，并将这个余数重新赋值给k。
k %= n就像是给k做了一次**“瘦身”**，剔除了所有整圈的无效动作，只保留了最后那点不到一圈的有效位移。

这是处理环形结构或周期性移动问题时的“标准动作”。

# 定义一个辅助函数：反转数组的指定区间defreverse(l:int,r:int):whilel<r:nums[l],nums[r]=nums[r],nums[l]l+=1r-=1

这一段代码是“原地反转数组”的核心逻辑。你可以把它想象成两个人在数组的两端，互相交换手里的东西，然后不断向中间靠拢。

我们可以通过物理动作、语法拆解和模拟运行三个维度来彻底理解它。

1. 物理动作：对撞指针

这段代码使用的是“对撞双指针”技巧：

• l(left): 指向待反转区间的“头”。
• r(right): 指向待反转区间的“尾”。

动作描述：

1. 交换l和r指向的元素。
2. l向右走一步 (l += 1)，r向左走一步 (r -= 1)。
3. 只要l还在r的左边（while l < r），就重复这个动作。
4. 当l和r相遇或者交叉时，整个区间就反转完成了。

2. Python 语法拆解：一行交换

代码中这一行非常“Pythonic”：
nums[l], nums[r] = nums[r], nums[l]

在很多其他语言（如 C++ 或 Java）中，交换两个变量需要一个中间人temp：

temp=nums[l]nums[l]=nums[r]nums[r]=temp

但在 Python 中，这一行代码利用了元组拆包 (Tuple Unpacking)：

• 先在内存里把等号右边的(nums[r], nums[l])打包成一个临时元组。
• 再同时赋值给等号左边的位置。
• 优点：简洁，且不会发生“先覆盖后丢失”的问题。

3. 实例模拟

假设数组是[1, 2, 3, 4]，我们调用reverse(0, 3)：

• 初始状态：l=0(值 1),r=3(值 4)。
  • 1 < 3成立，进入循环。
  • 交换：数组变为[4, 2, 3, 1]。
  • 移动：l变为 1,r变为 2。
• 第二轮：l=1(值 2),r=2(值 3)。
  • 1 < 2成立，进入循环。
  • 交换：数组变为[4, 3, 2, 1]。
  • 移动：l变为 2,r变为 1。
• 结束：l=2, r=1，此时l < r不再成立，跳出循环。

4. 为什么这个函数要在rotate内部定义？

在 Python 中，这叫嵌套函数 (Nested Function)。

• 封装性：反转逻辑只在轮转数组时用到，定义在里面可以让外面的代码更整洁。
• 闭包特性：内部函数reverse可以直接访问外部函数的变量nums，不需要把整个数组当参数传来传去，写起来很方便。

总结

这个reverse函数就像是一个“镜像翻转器”。在 189 题中，我们通过精准控制l和r的起始位置，实现了对数组不同部分的翻转：

1. reverse(0, n - 1)：翻转整个大镜像。
2. reverse(0, k - 1)：翻转前kkk个小镜像。
3. reverse(k, n - 1)：翻转后面剩下的镜像。

这种通过“对称性”来解决“位移”问题的思路是非常精妙。