题目描述
思路解析动画文字版
记住这套「分三趟、每趟从头扫、各收一类」,下面每一帧都在套它。
第 1 趟:从头扫,收所有 < 10 的元素,按原序放进输出的最前段。
第 0 位是 9,属于「小于 10」这一类,按原序抄进输出,现在 输出 = [9]。
第 1 位的 12 属于「大于 10」那类,归后面的趟收,本趟先放着。
第 2 位是 5,属于「小于 10」这一类,按原序抄进输出,现在 输出 = [9, 5]。
第 3 位的 10 属于「等于 10」那类,归后面的趟收,本趟先放着。
第 4 位的 14 属于「大于 10」那类,归后面的趟收,本趟先放着。
第 5 位是 3,属于「小于 10」这一类,按原序抄进输出,现在 输出 = [9, 5, 3]。
第 6 位的 10 属于「等于 10」那类,归后面的趟收,本趟先放着。
第 2 趟:再从头扫一遍,收所有 = 10 的元素,按原序接在小于段后面。
第 0 位的 9 已经在前面的「小于 10」段里收过了,本趟只收「等于 10」,所以跳过。
第 1 位的 12 属于「大于 10」那类,归后面的趟收,本趟先放着。
第 2 位的 5 已经在前面的「小于 10」段里收过了,本趟只收「等于 10」,所以跳过。
第 3 位是 10,属于「等于 10」这一类,按原序抄进输出,现在 输出 = [9, 5, 3, 10]。
第 4 位的 14 属于「大于 10」那类,归后面的趟收,本趟先放着。
第 5 位的 3 已经在前面的「小于 10」段里收过了,本趟只收「等于 10」,所以跳过。
第 6 位是 10,属于「等于 10」这一类,按原序抄进输出,现在 输出 = [9, 5, 3, 10, 10]。
第 3 趟:最后从头扫,收所有 > 10 的元素,按原序接到输出末尾。
第 0 位的 9 已经在前面的「小于 10」段里收过了,本趟只收「大于 10」,所以跳过。
第 1 位是 12,属于「大于 10」这一类,按原序抄进输出,现在 输出 = [9, 5, 3, 10, 10, 12]。
第 2 位的 5 已经在前面的「小于 10」段里收过了,本趟只收「大于 10」,所以跳过。
第 3 位的 10 已经在前面的「等于 10」段里收过了,本趟只收「大于 10」,所以跳过。
第 4 位是 14,属于「大于 10」这一类,按原序抄进输出,现在 输出 = [9, 5, 3, 10, 10, 12, 14]。
第 5 位的 3 已经在前面的「小于 10」段里收过了,本趟只收「大于 10」,所以跳过。
第 6 位的 10 已经在前面的「等于 10」段里收过了,本趟只收「大于 10」,所以跳过。
三趟扫完,输出就是 [9,5,3,10,10,12,14]。每段都是从头扫收集的,所以段内顺序和原数组完全一致,这就是「稳定」划分。
边界先想清:单元素、全大于、全小于时,原序都原样保留。
两个高频追问,重点区分「保序 vs 可交换」。
参考代码
from typing import Listclass 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]复杂度
- 时间:O(n),扫三遍数组,仍是线性
- 空间:O(n),一个长度 n 的输出数组
易错点
面试追问把动画讲成自己的话
追问能不能不用额外数组、原地 O(1) 空间完成?
追问和「荷兰国旗问题(LC75)」有什么区别?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题