LeetCode 2161中等数组分区
根据给定数字划分数组 图解题解
这道题到底在问什么
给定整数数组 nums 与整数 pivot，返回稳定划分后的数组：< pivot 的元素在前、= pivot 的居中、> pivot 的在后，三段各自保持原相对顺序。
- 输入
- nums=[9,12,5,10,14,3,10], pivot=10
- 输出
- [9,5,3,10,10,12,14]
- 输入
- nums=[-3,4,3,2], pivot=2
- 输出
- [-3,2,4,3]
最优解：一步一步想明白
- 3记住这套「分三趟、每趟从头扫、各收一类」，下面每一帧都在套它。
- 4第 1 趟：从头扫，收所有 < 10 的元素，按原序放进输出的最前段。
- 5第 0 位是 9，属于「小于 10」这一类，按原序抄进输出，现在 输出 = [9]。
- 6第 1 位的 12 属于「大于 10」那类，归后面的趟收，本趟先放着。
- 7第 2 位是 5，属于「小于 10」这一类，按原序抄进输出，现在 输出 = [9, 5]。
- 8第 3 位的 10 属于「等于 10」那类，归后面的趟收，本趟先放着。
- 9第 4 位的 14 属于「大于 10」那类，归后面的趟收，本趟先放着。
- 10第 5 位是 3，属于「小于 10」这一类，按原序抄进输出，现在 输出 = [9, 5, 3]。
- 11第 6 位的 10 属于「等于 10」那类，归后面的趟收，本趟先放着。
- 12第 2 趟：再从头扫一遍，收所有 = 10 的元素，按原序接在小于段后面。
- 13第 0 位的 9 已经在前面的「小于 10」段里收过了，本趟只收「等于 10」，所以跳过。
- 14第 1 位的 12 属于「大于 10」那类，归后面的趟收，本趟先放着。
- 15第 2 位的 5 已经在前面的「小于 10」段里收过了，本趟只收「等于 10」，所以跳过。
- 16第 3 位是 10，属于「等于 10」这一类，按原序抄进输出，现在 输出 = [9, 5, 3, 10]。
- 17第 4 位的 14 属于「大于 10」那类，归后面的趟收，本趟先放着。
- 18第 5 位的 3 已经在前面的「小于 10」段里收过了，本趟只收「等于 10」，所以跳过。
- 19第 6 位是 10，属于「等于 10」这一类，按原序抄进输出，现在 输出 = [9, 5, 3, 10, 10]。
- 20第 3 趟：最后从头扫，收所有 > 10 的元素，按原序接到输出末尾。
- 21第 0 位的 9 已经在前面的「小于 10」段里收过了，本趟只收「大于 10」，所以跳过。
- 22第 1 位是 12，属于「大于 10」这一类，按原序抄进输出，现在 输出 = [9, 5, 3, 10, 10, 12]。
- 23第 2 位的 5 已经在前面的「小于 10」段里收过了，本趟只收「大于 10」，所以跳过。
- 24第 3 位的 10 已经在前面的「等于 10」段里收过了，本趟只收「大于 10」，所以跳过。
- 25第 4 位是 14，属于「大于 10」这一类，按原序抄进输出，现在 输出 = [9, 5, 3, 10, 10, 12, 14]。
- 26第 5 位的 3 已经在前面的「小于 10」段里收过了，本趟只收「大于 10」，所以跳过。
- 27第 6 位的 10 已经在前面的「等于 10」段里收过了，本趟只收「大于 10」，所以跳过。
- 28三趟扫完，输出就是 [9,5,3,10,10,12,14]。每段都是从头扫收集的，所以段内顺序和原数组完全一致，这就是「稳定」划分。
⚠️ 容易写错的地方
✗ 错：用快排式双指针交换来分区
✓ 对：老老实实从头扫、按序收集
交换会打乱同段内的相对顺序，本题要求「稳定」，一乱就错
✗ 错：把等于 pivot 的并进某一边
✓ 对：等于 pivot 单独成中间段
题目要求三段：小于、等于、大于，等于项必须居中独立
✗ 错：一趟边扫边往同一结果数组里一次归位
✓ 对：分三趟各收一类，或一趟分三个临时桶再拼
想在单个结果数组里边扫边定位,中间段位置未定很麻烦;三趟收集(或三桶后拼)都稳定且 O(n),本课选三趟图直观
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
return [x for x in nums if x < pivot] + [x for x in nums if x == pivot] + [x for x in nums if x > pivot]C++
#include <vector>
using namespace std;
class Solution {
public:
vector<int> pivotArray(vector<int>& nums, int pivot) {
vector<int> ans;
for (int x : nums) if (x < pivot) ans.push_back(x);
for (int x : nums) if (x == pivot) ans.push_back(x);
for (int x : nums) if (x > pivot) ans.push_back(x);
return ans;
}
};Java
import java.util.*;
class Solution {
public int[] pivotArray(int[] nums, int pivot) {
int[] ans = new int[nums.length];
int idx = 0;
for (int x : nums) if (x < pivot) ans[idx++] = x;
for (int x : nums) if (x == pivot) ans[idx++] = x;
for (int x : nums) if (x > pivot) ans[idx++] = x;
return ans;
}
}复杂度
时间
O(n)
扫三遍数组，仍是线性
空间
O(n)
一个长度 n 的输出数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 根据给定数字划分数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不用额外数组、原地 O(1) 空间完成？+
如果要求稳定，原地很难做到 O(1)：稳定地把元素归位通常仍需额外空间或更复杂的旋转操作。本题数据范围允许用一个 O(n) 输出数组，三趟扫描最清晰，是面试里的标准答法。
和「荷兰国旗问题（LC75）」有什么区别？+
LC75 把 0/1/2 三色就地分区、不要求段内稳定，所以能用三指针一趟交换 O(1) 空间；本题要求每段保持原相对顺序，不能交换，改用三趟按序收集。一个不保序可就地、一个要保序需额外数组。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 根据给定数字划分数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。