企业官网建设流程全解析

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]

逐个位置检查一下：

所以这个数组里的“奇怪球”集合是{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]走一遍，主要状态变化如下：

最终数组前三位[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

运行过程如下：

最终结果[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. 最后聊一点个人体会

我最初写双指针题目的时候，特别喜欢背模板，看到“数组左右移动”就直接套代码。后来发现很多时候代码能跑，但换一个变体就懵了，比如这道“奇怪球”题把判断条件换成“奇偶不一致”之后，左右指针的写法其实没变，只是判断函数变了。

这个事后复盘让我意识到，双指针真正值钱的地方，不是那几行交换代码，而是“用两个指针划分区域”的思维。指针动了，区域就变了；区域变了，循环不变量要能接得住。只要把这个问题想清楚，代码写出来是水到渠成的事。

如果你也是准备面试或者刚入门算法，建议把这道“奇怪球”题当成一个起点。先手动模拟一遍左右指针，再手动模拟一遍快慢指针，然后尝试改一改判定条件，比如“把奇偶错位的球放到数组后面”，或者“把所有偶数编号的球放到前面”，多跑几个测试用例。等你能够独立把这几个变体都写出来，双指针的分区思想基本就吃透了。