多指针法：荷兰国旗问题的多颜色扩展——将数组按多阈值分区（Multiple Pivot Partitioning）

题目描述

我们通常遇到的荷兰国旗问题（Dutch National Flag Problem）是将一个数组按某个目标值（pivot）划分为“小于”、“等于”、“大于”三个区域。
现在，我们将其扩展为多阈值分区（Multiple Pivot Partitioning）问题：
给定一个包含 n 个整数的数组 nums，以及一个长度为 m 的严格递增阈值序列 pivots = [p1, p2, …, pm]，要求将数组原地重新排列，使得所有元素按阈值序列自然分区：

• 所有小于 p1 的元素出现在最前面；
• 所有等于 p1 的元素紧随其后（若存在）；
• 接着是大于 p1 但小于 p2 的元素；
• 接着是等于 p2 的元素；
• 以此类推，最后是所有大于 pm 的元素。

注意：

1. 分区后，同一阈值区间内的元素不需要保持原有顺序（即排序是不稳定的）。
2. 要求时间复杂度为 O(n * m) 或更优，空间复杂度为 O(1)（原地修改）。

例如：
输入：nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5], pivots = [3, 5]
输出（一种可能）：[1, 1, 2, 3, 3, 4, 5, 5, 5, 9, 6]
分区说明：

• 小于3的区域：1, 1, 2
• 等于3的区域：3, 3
• 大于3且小于5的区域：4
• 等于5的区域：5, 5, 5
• 大于5的区域：9, 6

解题过程

步骤1：问题理解与核心难点

我们需要将数组按多个阈值划分成 (2m + 1) 个区间（每个阈值有“等于”区间，阈值之间有“介于”区间，以及首尾的“小于”和“大于”区间）。
直接多次调用标准的三路分区（针对每个 pivot）会导致已排好的区域被破坏，因为每次分区会打乱其他区间的顺序。
因此，我们需要一次性扫描数组，同时维护多个指针来标记各个区间的边界。

步骤2：从简单情况推导

先回顾标准的荷兰国旗三路分区（一个 pivot）：用三个指针 low, mid, high，将数组划分为 <p、=p、>p 三部分。
现在假设有两个 pivot：p1 和 p2（p1 < p2）。我们需要划分出 5 个区间：

1. < p1
2. = p1
3. p1 < x < p2
4. = p2
5. > p2

我们可以扩展三路分区的思想：使用多个指针来标记每个区间的右边界（不包含）。
对于 m 个阈值，我们会有 (2m + 1) 个区间，因此需要 (2m + 2) 个指针（包括数组起始和末尾）。

步骤3：指针设计与初始化

设数组索引从 0 到 n-1。
定义指针数组 bounds，长度为 (2m + 2)，其中：

• bounds[0] = 0（整个数组的起始）
• bounds[1] 指向“小于 p1”区间的末尾（不包含）
• bounds[2] 指向“等于 p1”区间的末尾
• bounds[3] 指向“p1 < x < p2”区间的末尾
• ……以此类推。
• bounds[2m + 1] = n（整个数组的末尾）

初始时，除了 bounds[0] = 0 和 bounds[2m + 1] = n，其余指针都指向 0（表示对应区间为空）。
我们还需要一个“当前处理指针” current，从 0 开始向右扫描数组。

步骤4：分区过程（以两个 pivot 为例）

假设 pivots = [p1, p2]，区间编号 0~4 对应上面列出的 5 个区间。
指针 bounds[0..5] 分别表示各个区间的末尾（不包含），初始为 [0, 0, 0, 0, 0, n]。

我们扫描数组元素 nums[current]：

1. 若元素 < p1：它属于区间 0。
   • 为了放入区间 0，我们需要将区间 0 后的所有元素向后“旋转”一位，腾出位置。
   • 具体操作：将区间 1、2、3、4 的所有元素整体右移一位，然后将当前元素放入区间 0 末尾。
   • 更新 bounds[1..5] 分别加 1。
   • current 也加 1（因为当前元素已处理并移到了前面）。
2. 若元素 = p1：属于区间 1。
   • 将区间 2、3、4 的元素整体右移一位，放入区间 1 末尾。
   • 更新 bounds[2..5] 加 1。
   • current 加 1。
3. 若 p1 < 元素 < p2：属于区间 2。
   • 将区间 3、4 的元素整体右移一位，放入区间 2 末尾。
   • 更新 bounds[3..5] 加 1。
   • current 加 1。
4. 若元素 = p2：属于区间 3。
   • 将区间 4 的元素整体右移一位，放入区间 3 末尾。
   • 更新 bounds[4..5] 加 1。
   • current 加 1。
5. 若元素 > p2：属于区间 4。
   • 不需要移动其他区间，直接将其保留在原位（因为区间 4 就在最后）。
   • 只需将 bounds[5] 减 1？不对，这里需要仔细处理。

实际上，更高效的做法是从右向左填充最后的大区间，但为了保持一次扫描且原地，我们采用另一种策略：
当遇到属于区间 k 的元素时，我们将它交换到区间 k 的当前位置，并扩展区间 k 的边界，但需要保证不影响未处理的元素。

步骤5：优化为一次遍历交换策略

我们可以这样设计：

• 维护 bounds[i] 表示区间 i 的末尾（不包含）。
• 从 current = 0 开始扫描，直到 current 遇到最后一个非最终区间的边界（即 bounds[2m]）。
• 当遇到元素时，判断它属于哪个区间 j（通过依次与 pivots 比较）。
• 如果 j 就是当前 current 所在的区间（即 bounds[j] <= current < bounds[j+1]），说明它已经在正确位置，直接 current++。
• 否则，需要将这个元素交换到区间 j 的末尾（即 bounds[j] 位置），然后将被交换过来的元素（原来在 bounds[j] 位置的元素）作为新元素继续处理。
• 交换后，区间 j 的边界 bounds[j] 向右扩展一位（即 bounds[j]++），并且所有在区间 j 之后的区间边界也要依次右移一位（保持连续性）。
• 注意：current 不增加，因为我们还要处理被交换过来的新元素。

这种方法的本质是将每个元素直接放入它最终所属的区间，通过交换避免大规模数据移动。

步骤6：算法伪代码（通用 m 个阈值）

function multiPivotPartition(nums, pivots):
    m = length(pivots)
    bounds = array of size (2*m + 2) filled with 0
    bounds[0] = 0
    bounds[2*m + 1] = n
    
    current = 0
    while current < bounds[2*m + 1]:
        x = nums[current]
        # 确定 x 属于哪个区间 j
        j = 0
        if x < pivots[0]:
            j = 0
        else:
            for k from 0 to m-1:
                if x == pivots[k]:
                    j = 2*k + 1
                    break
                if k < m-1 and x < pivots[k+1]:
                    j = 2*k + 2
                    break
            if j == 0: # 说明 x > pivots[m-1]
                j = 2*m
        
        # 如果 current 已经在区间 j 内，则跳过
        if bounds[j] <= current < bounds[j+1]:
            current++
            continue
        
        # 否则，将 x 交换到区间 j 的末尾（即 bounds[j] 位置）
        swap nums[current] with nums[bounds[j]]
        # 扩展区间 j 及其后所有区间的边界
        for t from j to 2*m:
            bounds[t+1]++

注意：当 current 遇到 bounds[2*m + 1]（即数组末尾）时停止，因为最后区间（大于 pm）已经自然就位。

步骤7：时间与空间复杂度

• 每个元素在一次扫描中被处理（交换或跳过）。
• 每次确定元素所属区间需要 O(m) 次比较（可通过二分查找优化到 O(log m)，因为 pivots 有序）。
• 每次交换后更新边界需要 O(m) 时间（因为需要后移多个边界指针）。
• 总时间复杂度：O(n * m)（如果使用简单线性比较和边界更新）。
• 若使用二分查找确定区间，则比较成本降为 O(n log m)，但边界更新仍需 O(n * m)（因为可能涉及多个指针移动）。
• 在实际优化中，可通过维护“区间边界增量”来减少更新代价，但实现较复杂。
• 空间复杂度：O(1) 原地（除了存放边界的 O(m) 辅助数组，但 m 通常远小于 n）。

步骤8：举例验证

以 nums = [3,1,4,1,5,9,2,6,5,3,5], pivots = [3,5] 为例，m=2，区间数 5。
初始 bounds = [0,0,0,0,0,11]（11 是数组长度）。

逐步执行（简述）：

1. current=0, x=3，属于区间1（等于3），交换到 bounds[1]=0 位置（即自身），更新 bounds[1..5] 为 [1,1,1,1,1,11]，current++。
2. current=1, x=1，属于区间0（小于3），交换到 bounds[0]=0 位置（与 nums[0]=3 交换），数组变为 [1,3,4,1,5,...]，更新 bounds[0..5] 为 [1,2,2,2,2,11]，current 不变（仍需处理交换来的3）。
3. current=1, x=3，属于区间1，且已在区间1内（因为 bounds[1]=1, bounds[2]=2），current++。
   …（继续直到结束）

最终得到分区数组。

总结

本题将经典的荷兰国旗三路分区推广到多阈值情况，通过维护多个区间边界指针，在一次遍历中通过交换将元素归位到相应区间。
虽然时间复杂度与阈值数量 m 相关，但在 m 不大时是高效的原位分区算法，适用于多级分类问题，如按多个离散阈值快速分组数据。