根据给定数字划分数组

难度: Medium

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

所有小于 pivot 的元素都出现在所有大于 pivot 的元素之前。
所有等于 pivot 的元素都出现在小于和大于 pivot 的元素中间。
小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
- 更正式的，考虑每一对 p_i，p_j ，p_i 是初始时位置 i 元素的新位置，p_j 是初始时位置 j 元素的新位置。对于小于 pivot 的元素，如果 i < j 且 nums[i] < pivot 和 nums[j] < pivot 都成立，那么 p_i < p_j 也成立。类似的，对于大于 pivot 的元素，如果 i < j 且 nums[i] > pivot 和 nums[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 中的一个元素。

Submission

运行时间: 68 ms

内存: 31.4 MB

from typing import List

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        less = []
        equal = []
        greater = []
        
        for num in nums:
            if num < pivot:
                less.append(num)
            elif num == pivot:
                equal.append(num)
            else:
                greater.append(num)
        
        return less + equal + greater

Explain

该题解使用了三个列表：less、equal 和 greater，来分别存储小于、等于和大于给定枢轴（pivot）的元素。通过遍历输入数组 nums，将每个元素分类后放入相应的列表。最后，将这三个列表依次合并，以得到符合题目要求的数组，其中小于 pivot 的元素在前，等于 pivot 的元素在中间，大于 pivot 的元素在后，同时保留了各自元素的相对顺序。

时间复杂度: O(n)

空间复杂度: O(n)

from typing import List

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        less = []  # 存储小于pivot的元素
        equal = []  # 存储等于pivot的元素
        greater = []  # 存储大于pivot的元素
        
        for num in nums:  # 遍历数组中的每个元素
            if num < pivot:
                less.append(num)  # 如果元素小于pivot，则加入less列表
            elif num == pivot:
                equal.append(num)  # 如果元素等于pivot，则加入equal列表
            else:
                greater.append(num)  # 如果元素大于pivot，则加入greater列表
        
        return less + equal + greater  # 合并三个列表并返回

Explore

在pivotArray方法的实现中，不需要特别处理nums数组为空的情况。由于三个列表（less, equal, greater）在方法开始时均被初始化为空列表，如果输入数组nums为空，遍历操作将直接跳过，最终方法返回的也将是一个空列表，即合并后的结果同样为空列表。这种处理自然地符合了对空输入数组的处理需求。

是的，这种分类方法会保持数组中重复元素的相对顺序不变。方法通过逐个遍历数组元素并根据它们与pivot的关系加入到相应的列表中，这保证了元素在各自列表中的顺序与原数组中的顺序一致。由于最终输出数组是通过按顺序合并这三个列表生成的，因此原数组中元素的相对位置被保留。这种特性在算法中称为稳定性。

如果pivot值在数组nums中不存在，这个算法的处理方式并无特殊之处。算法仍然会遍历整个数组，将每个元素与pivot进行比较，并按照比较结果添加到less、equal或greater列表中。由于pivot不存在于数组中，equal列表将保持为空。最终返回的数组将只包含less和greater列表的元素，按原先的顺序排列。

在处理极端不均匀的数据时，这种分类方法的效率和空间使用将受到影响。例如，如果大多数元素都小于pivot，那么less列表将变得很大，而equal和greater列表可能非常小或为空。这种情况下，空间使用增加，因为需要额外的空间来存储每个列表中的元素。尽管如此，从时间复杂度角度来看，方法仍然是有效的，因为处理每个元素的时间是常量，整体复杂度仍为O(n)。但在最坏情况下，空间复杂度也为O(n)，这可能在极端情况下导致不必要的内存使用。