What is the simplest way to partition an array according to a given pivot?

Use three separate lists for elements less than, equal to, and greater than the pivot, then merge them to preserve order.

Does this solution maintain the original order of elements?

Yes, the two-pointer scanning with bucket collection ensures the relative order within each group is preserved.

Can this problem be solved in-place without extra space?

In-place solutions exist but require careful stable partitioning to avoid breaking relative ordering.

What are common mistakes when implementing pivot partitioning?

Breaking relative order, misplacing pivot elements, or using nested loops that increase time complexity.

How does the two-pointer scanning pattern apply here?

It efficiently separates elements into three categories in a single pass while tracking invariants, exactly matching this problem's requirement.

#2161

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

根据给定数字划分数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立：所有小于 pivot 的元素都出现在所有大于 pivot 的元素之前。所有等于 pivot 的元素都出现在小于和大于 pivot 的元素中间。小于 pivot 的元素…

数组双指针模拟

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立：

所有小于 pivot 的元素都出现在所有大于 pivot 的元素之前。
所有等于 pivot 的元素都出现在小于和大于 pivot 的元素中间。
小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
- 更正式的，考虑每一对 p_i，p_j ，p_i 是初始时位置 i 元素的新位置，p_j 是初始时位置 j 元素的新位置。如果 i < j 且两个元素都小于（或大于）pivot，那么 p_i < p_j 。

请你返回重新排列 nums 数组后的结果数组。

示例 1：

输入：nums = [9,12,5,10,14,3,10], pivot = 10
输出：[9,5,3,10,10,12,14]
解释：
元素 9 ，5 和 3 小于 pivot ，所以它们在数组的最左边。
元素 12 和 14 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [9, 5, 3] 和 [12, 14] ，它们在结果数组中的相对顺序需要保留。

示例 2：

输入：nums = [-3,4,3,2], pivot = 2
输出：[-3,2,4,3]
解释：
元素 -3 小于 pivot ，所以在数组的最左边。
元素 4 和 3 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [-3] 和 [4, 3] ，它们在结果数组中的相对顺序需要保留。

提示：

1 <= nums.length <= 10⁵
-10⁶ <= nums[i] <= 10⁶
pivot 等于 nums 中的一个元素。

lightbulb

解题思路

方法一：模拟

我们可以遍历数组 $\textit{nums}$ ，按顺序找出所有小于 $\textit{pivot}$ 的元素，所有等于 $\textit{pivot}$ 的元素，以及所有大于 $\textit{pivot}$ 的元素，然后将它们按照题目要求的顺序拼接起来。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $\textit{nums}$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        a, b, c = [], [], []
        for x in nums:
            if x < pivot:
                a.append(x)
            elif x == pivot:
                b.append(x)
            else:
                c.append(x)
        return a + b + c

speed

复杂度分析

指标	值
时间	complexity is O(N) since each element is visited once. Space complexity is O(N) for storing elements in three separate lists before merging.
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Do you track elements less than, equal to, and greater than the pivot separately?
question_mark
Can you maintain the original relative ordering of elements in a single pass?
question_mark
Are you considering both time efficiency and space trade-offs for this two-pointer pattern?

warning

常见陷阱

外企场景

error
Trying to do in-place swaps without tracking order, which breaks relative ordering.
error
Confusing elements equal to the pivot with either smaller or larger group.
error
Using nested loops, increasing time complexity unnecessarily.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Partition using in-place stable partition algorithms to reduce space but maintain order.
arrow_right_alt
Extend to multiple pivots, sorting by multiple thresholds with stable grouping.
arrow_right_alt
Apply to linked lists instead of arrays to practice pointer manipulation.

help

常见问题

外企场景

继续练习

#2149 按符号重排数组 #2109 向字符串添加空格 #2105 给植物浇水 II