从奇怪球算法吃透双指针：原地分区与奇偶性判断

2024年9月21日刷题群里有人甩出一道题名字很唬人叫“奇怪球算法”。刚看到的时候我还以为是某种物理小游戏点进去才发现这是一道典型的双指针练手题核心逻辑简单到让人怀疑是不是被题面包装骗了。题目大意是这样一串小球排成一列每个位置有一个下标每个球上写着一个整数编号。如果某个球的编号和它所在下标的奇偶性不一致这个球就是“奇怪球”。现在要求把所有奇怪球全部挪到数组左边普通球挪到右边并且只能原地调整时间复杂度 O(n)额外空间 O(1)。这种题非常适合准备算法面试的人拿来练手也能帮你把双指针的“左指针、右指针、快慢指针”彻底搞明白。我复盘完这道题之后最大的感受是双指针不是背模板而是先把“指针到底代表什么”想清楚。下面把这套完整思路拆开讲。1. 奇怪球问题先搞清楚题目在说什么1.1 什么是奇怪球座位号与编号的奇偶性对不上题目里说的“奇怪球”不是球长得奇怪而是“球的位置”和“球上的编号”出现了错位。我们用下标 0 开始计数。位置 0、2、4 这种偶数下标就相当于是“偶数座位”位置 1、3、5 这种奇数下标就相当于是“奇数座位”。一个球坐在座位上如果座位是奇数但球上编号是偶数那这个球放得就不合适。反过来也一样偶数座位放着奇数编号的球同样不合适。用一段布尔表达式来描述就是is_strange(i, x) (i % 2) ! (x % 2)如果这个表达式成立下标 i 位置上的球 x 就是题目里要找的“奇怪球”。用大白话说奇数位应该放奇数编号偶数位应该放偶数编号对不上的统统有问题。有人可能会觉得这个定义很生硬但在算法题里这种“自定义规则”太常见了。核心不在于“奇怪球”这个名字而在于“按某个条件把元素分成两部分并把满足条件的全部挪到一侧”。1.2 一个能跑通全过程的输入输出示例直接上一个例子假设输入数组是nums [2, 4, 3, 1, 5]逐个位置检查一下下标座位性质球上编号编号性质是否符合规则0偶2偶正常球1奇4偶奇怪球2偶3奇奇怪球3奇1奇正常球4偶5奇奇怪球所以这个数组里的“奇怪球”集合是{4, 3, 5}正常球集合是{2, 1}。最终目标不是让数组完全有序而是把所有奇怪球都放到数组前面。一个合法输出可以是[4, 5, 3, 1, 2]前三位全是奇怪球后两位全是正常球符合要求。如果题目不要求保持相对顺序那这种结果就完全可以通过。1.3 为什么不能一上来就排序一般看到“挪到左边/右边”这种需求很多人第一反应是排序。但仔细想想题目并不是要你对所有数字做全局排序它只是做一次“按条件分区”。排序的复杂度至少是 O(n log n)不符合题目对 O(n) 的要求。另外排序会把元素的原有顺序彻底打乱。比如同样一组球排序后编号从 1 到 5虽然看起来整齐了但“哪些是奇怪球”并不会因为你排序之后就发生变化。就算你强行排序最后还是要额外判断一遍奇偶性才能分区属于绕了一大圈却没用对工具。这类“把符合某条件的元素放到某一侧”的问题最自然的解法就是双指针。因为双指针可以在一次遍历过程中通过交换元素完成原地分区既不消耗额外空间又只扫描一趟。2. 双指针为什么是正解先想想暴力解法2.1 暴力解辅助数组两遍扫描在没有原地限制的情况下最朴素的解法是开一个临时数组第一遍遍历收集所有奇怪球第二遍遍历收集所有正常球然后拼接。代码写出来大概是这样def strange_balls_extra(nums): n len(nums) result [] for i, x in enumerate(nums): if (i % 2) ! (x % 2): result.append(x) for i, x in enumerate(nums): if (i % 2) (x % 2): result.append(x) nums[:] result return nums这个解法的时间复杂度确实是 O(n)而且实现简单、逻辑清晰还能保持两类球的相对顺序。但它的问题也很明显额外用了一个临时数组空间复杂度是 O(n)。如果数组长度是几百那无所谓。可要是这个数组是从生产环境的日志里拆出来的长度到几十万甚至上千万每个元素又是复杂对象多开一个等长数组就会带来很大的内存压力。这也是为什么很多算法面试题会强制要求 O(1) 额外空间的原因。2.2 双指针的直觉两个挡板把数组分成三块双指针的核心思想并不复杂。想象你面前有一条从传送带上传下来的小球队伍你手里有两个挡板。左挡板左边是已经确认的“奇怪球区域”右挡板右边是已经确认的“正常球区域”两个挡板中间是还没检查的区域。每一轮操作左边的检查者从左往右走遇到已经确定的奇怪球就直接跳过直到发现一个“混进正常区域”的球右边的检查者从右往左走遇到已经确定的正常球就直接跳过直到发现一个“混进奇怪区域”的球。两边都发现了“对不上号”的球之后把这两个球交换一下。交换之后左边那个位置就变成了奇怪球右边那个位置就变成了正常球。两个挡板往中间收一格中间待检查的区域就继续缩小。这个思路其实和快速排序里 partition 的过程非常像。区别在于快排 partition 用最后一个元素当基准而这里用的是题目自定义的奇偶性条件。2.3 双指针的三种常见形态很多人一开始接触双指针时会分不清“对撞指针”和“快慢指针”。这两种形态在这道题里都能用但适用场景不完全一样。形态指针移动方式典型用途是否容易保持相对顺序对撞指针一个从左往右一个从右往左两类元素分区、有序数组查找不稳定快慢指针两个都从左边出发一个快一个慢移动零、去重、环形链表检测对目标元素相对有序滑动窗口左右边界同向移动窗口动态变化最长子串、最小覆盖子串不关心相对顺序这道“奇怪球”题既可看成两类元素分区也可以用快慢指针来写。关键是先想清楚当前用哪一种形态更自然。对撞指针的好处是逻辑直观两个指针从两端往中间夹逼一轮循环下来数组就被分成了左右两块。快慢指针的好处是代码更短而且“奇怪球”自身的前后顺序能被保留代价是普通球之间的相对顺序可能会被打乱。具体怎么选取决于题目是否要求稳定。3. 两种双指针实现从代码到循环不变量3.1 判定“奇怪球”的细节先把这个函数写对在写主循环之前先把判断逻辑封装成一个独立函数能避免后面到处复制出错。def is_strange(index: int, value: int) - bool: return (index 1) ! (value 1)这里用位运算 1来判断奇偶性而不是% 2原因很简单 1直接取最低二进制位正数负数都能正确判断奇偶。比如-3 1的结果是 1说明它是奇数-4 1的结果是 0说明它是偶数。如果用取模不同语言对负数取模的规则还不一样写起来容易踩坑。判奇偶这种场景用位运算是最稳妥的。小括号最好别省。虽然 Python 的运算符优先级里比!高但稍微复杂一点的表达式多写一对括号能省掉很多不必要的阅读成本。3.2 左右双指针法代码最短的对撞实现左右双指针的逻辑是让 left 从左边找到第一个“正常球”让 right 从右边找到第一个“奇怪球”然后交换它们。交换完成后left 位置一定是奇怪球right 位置一定是正常球再同时向中间移动。def strange_balls_two_pointers(nums): n len(nums) if n 2: return nums left, right 0, n - 1 while left right: while left right and is_strange(left, nums[left]): left 1 while left right and not is_strange(right, nums[right]): right - 1 if left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 return nums用之前的输入[2, 4, 3, 1, 5]走一遍主要状态变化如下轮数left 位置right 位置操作数组状态初始04无[2, 4, 3, 1, 5]104交换[5, 4, 3, 1, 2]213left 连续移动到 left3和 right 相遇[5, 4, 3, 1, 2]结束33无[5, 4, 3, 1, 2]最终数组前三位[5, 4, 3]全是奇怪球后两位[1, 2]全是正常球满足要求。3.3 快慢指针法同向遍历也能完成任务另一种写法是快慢指针。fast 负责从头到尾扫描slow 指向“下一个奇怪球应该放到的位置”。每遇到一个奇怪球就把它交换到 slow 指向的位置然后 slow 向后挪一格。def strange_balls_slow_fast(nums): n len(nums) slow 0 for fast in range(n): if is_strange(fast, nums[fast]): nums[slow], nums[fast] nums[fast], nums[slow] slow 1 return nums运行过程如下fastnums[fast]是否是奇怪球操作数组状态02否fast 前进[2, 4, 3, 1, 5]14是交换下标 0 和 1slow1[4, 2, 3, 1, 5]23是交换下标 1 和 2slow2[4, 3, 2, 1, 5]31否fast 前进[4, 3, 2, 1, 5]45是交换下标 2 和 4slow3[4, 3, 5, 1, 2]最终结果[4, 3, 5, 1, 2]前三位是奇怪球后两位是普通球。如果从“保留奇怪球相对顺序”这个角度看快慢指针比左右交换法更好因为每个奇怪球都是按扫描顺序依次被放到前面的。3.4 复杂度与循环不变量写双指针前先想清楚这几点先看复杂度。无论是左右指针还是快慢指针每个元素最多被访问常数次所以时间复杂度都是 O(n)。额外只用了几个变量空间复杂度 O(1)。这一点完全符合题目要求。再看循环不变量。写双指针代码容易晕是因为没把“每个区间里放什么”定义清楚。左右指针的循环不变量是[0, left)区间内全部是奇怪球。(right, n-1]区间内全部是正常球。[left, right]是尚未处理的区域。每次交换后左右两边的已处理区域都会扩大未处理区域会收缩。这个过程持续到 left 和 right 交错为止。快慢指针的循环不变量是[0, slow)区间内全部是已经遇到的奇怪球。[slow, fast)区间内没有未处理的奇怪球。[fast, n)是尚未扫描的区域。每次 fast 遇到奇怪球后交换到 slow 位置并让 slow 加一这个不变量始终成立。如果能在动手写代码前先把类似的不变量用一句话写出来代码基本不会写错。4. 实战踩坑记录这些细节能让你少烧半天脑4.1 内层 while 忘加边界条件直接数组越界左右指针很容易犯的一个错误是内层 while 只判断条件忘了加left right。# 错误写法 while is_strange(left, nums[left]): left 1如果整个数组全是奇怪球left 会一路加下去直到越界。正确写法必须在循环条件里带上边界判断while left right and is_strange(left, nums[left]): left 1同理右侧的指针也要控制边界。边界判断不是可有可无的防备而是保证程序安全的必要部分。4.2 负数球编号的奇偶性判断如果数组里允许出现负数判断奇偶性时踩坑的概率会明显上升。比如用value % 2 0判断偶数在 Python 里其实是没问题的因为负数取模的结果仍然能区分奇偶。但不同语言规则不同换到别的语言写起来会让人困惑。统一用value 1能直接绕过这个问题。位运算提取最低位和正负号无关代码也更简洁。判断号函数写成一行的优势在这时候就体现出来了。假如把奇偶判断逻辑内联到主循环里出现负数时可能还得修两处三处。封装后只需要改一个函数测一个函数。4.3 交换后指针没有移动导致死循环另一种常见情况是交换完成后忘了移动指针。左右指针法里如果交换后不执行left 1和right - 1下一轮循环左指针还会停在原位置因为该位置已经变成正常球了左指针会被内层 while 直接放行但外层 while 仍然成立最终可能导致无限循环。快慢指针法里不移动 slow 的问题更隐蔽。如果nums[fast]是奇怪球却没让 slow 自增下次遇到另一个奇怪球时就会覆盖同一个位置前面的结果被冲掉。所以交换和移动指针必须成对出现。4.4 用随机测试验证最终结果如果是在本地练习建议写一个简单的随机测试函数生成大量随机数组验证算法的输出是否满足要求。import random def is_valid(nums): n len(nums) split 0 while split n and is_strange(split, nums[split]): split 1 for i in range(split, n): if is_strange(i, nums[i]): return False return True for _ in range(10000): nums [random.randint(-10, 10) for _ in range(random.randint(0, 20))] strange_balls_two_pointers(nums) if not is_valid(nums): print(出错了, nums) break这种随机验证跑一遍比手算十个例子都管用。它能覆盖很多极端情况比如全奇怪球、全正常球、只有一个元素、负数、重复数字等。5. 从一个奇怪球到一整片双指针题5.1 移动零双指针最经典的入门题LeetCode 283 题“移动零”给定一个数组nums把所有的 0 移动到数组末尾同时保持非零元素的相对顺序。这个题用同向快慢指针非常顺手def move_zeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1 return nums这和“奇怪球”的快慢指针写法几乎一模一样。唯一区别是判断条件从“是否是奇怪球”变成了“是否不等于 0”。当你理解了慢指针是“下一个有效元素的写入位”这类题就都能看穿了。5.2 按奇偶排序目标从“奇怪球”换成“偶数”LeetCode 905 题“按奇偶排序数组”要求把偶数放在前面奇数放在后面。这在本质上也是双指针分区只是把“奇怪球”判断条件换成“是否是偶数”def sort_array_by_parity(nums): left, right 0, len(nums) - 1 while left right: while left right and nums[left] % 2 0: left 1 while left right and nums[right] % 2 ! 0: right - 1 if left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 return nums熟练之后你会发现左右指针就是一把万能螺丝刀。换不同判断条件就能解决很多看起来完全不同的题。5.3 荷兰国旗问题从两类变成三类如果把元素从两类变成三类比如数组里只有 0、1、2 三种颜色球要求排序成000...111...222那就需要三个指针。经典的荷兰国旗问题写法def sort_colors(nums): left, i, right 0, 0, len(nums) - 1 while i right: if nums[i] 0: nums[left], nums[i] nums[i], nums[left] left 1 i 1 elif nums[i] 2: nums[right], nums[i] nums[i], nums[right] right - 1 else: i 1 return nums这里有一个非常容易踩的坑当nums[i] 2交换到右边后i不能直接加一因为换回来的数可能还是 0 或 2需要继续判断。而nums[i] 0时却可以放心加一因为左侧区域已经确认全是 0换回来的 0 不会破坏状态。5.4 同向双指针的通用模板从“奇怪球”到“移动零”再到各种分区问题同向双指针其实有一个通用模板slow 0 for fast in range(n): if 满足某种条件: nums[slow], nums[fast] nums[fast], nums[slow] slow 1对撞指针也有一个通用模板left, right 0, n - 1 while left right: while left right and 左指针需要跳过: left 1 while left right and 右指针需要跳过: right - 1 if left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1把这些模板理解成“招式”不难难的是知道每一招背后的循环不变量是什么。把指针维护的区间含义搞清楚自然就能根据题目调整条件。6. 最后聊一点个人体会我最初写双指针题目的时候特别喜欢背模板看到“数组左右移动”就直接套代码。后来发现很多时候代码能跑但换一个变体就懵了比如这道“奇怪球”题把判断条件换成“奇偶不一致”之后左右指针的写法其实没变只是判断函数变了。这个事后复盘让我意识到双指针真正值钱的地方不是那几行交换代码而是“用两个指针划分区域”的思维。指针动了区域就变了区域变了循环不变量要能接得住。只要把这个问题想清楚代码写出来是水到渠成的事。如果你也是准备面试或者刚入门算法建议把这道“奇怪球”题当成一个起点。先手动模拟一遍左右指针再手动模拟一遍快慢指针然后尝试改一改判定条件比如“把奇偶错位的球放到数组后面”或者“把所有偶数编号的球放到前面”多跑几个测试用例。等你能够独立把这几个变体都写出来双指针的分区思想基本就吃透了。