不改变相对顺序的数组三向分区

---

在本文中，我们将对包含N个整数的数组进行三向分区。

该方法是使用三个队列。每个队列都将用于存储一部分元素。之后，我们可以从各自的队列中获取每一部分的元素，而不会改变元素的相对顺序。

问题陈述

给定一个包含N个整数的数组和一个范围[LOW, HIGH]，我们需要将数组分成三个部分，使得：

• 小于LOW的元素排在最前面

• 大于LOW且小于HIGH的元素排在中间。

• 大于HIGH的元素排在最后。

• 元素的相对顺序保持不变

示例

输入

arr = {3,1,5,10,3,7,2,5,6,8}, LOW = 3, HIGH = 7

输出

1 2 3 5 3 7 5 6 10 8

解释

这里，小于3的元素首先出现，然后是3到7之间的元素，最后是大于7的元素。元素的相对顺序保持不变。

输入

arr = {10,9,8,7,6,5,4,3,2,1}, LOW = 5, HIGH = 8

输出

4 3 2 1 8 7 6 5 10 9

解释

这里，小于5的元素首先出现，然后是5到8之间的元素，最后是大于8的元素。元素的相对顺序保持不变。

输入

arr = {4,3,3,5,6,3,100,321,45,54,5,6,1,2,3}, LOW = 5, HIGH = 10

输出

4 3 3 3 1 2 3 5 6 5 6 100 321 45 54

解释

这里，小于5的元素首先出现，然后是5到7之间的元素，最后是大于7的元素。元素的相对顺序保持不变。

方法1

在这种方法中，我们将使用三个队列数据结构来存储三个部分的元素，即小于LOW的、LOW和HIGH之间的、大于HIGH的。这也会保持元素的原始顺序。

算法

• 步骤1 - 遍历数组元素。

• 步骤2 - 将元素插入到相应的队列中。

• 步骤2.1 - 如果元素小于LOW，则将其插入队列1。

• 步骤2.2 - 如果元素在LOW和HIGH之间，则将其插入队列2。

• 步骤2.3 - 如果元素大于HIGH，则将其插入队列3。

• 步骤3.1 - 从队列1中弹出所有元素并将其添加到结果数组中。

• 步骤3.2 - 从队列2中弹出所有元素并将其添加到结果数组中。

• 步骤3.3 - 从队列3中弹出所有元素并将其添加到结果数组中。

• 步骤4 - 返回结果数组。

示例

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> ThreeWayPartition(vector<int> &arr,int LOW,int HIGH){
   queue<int> q1,q2,q3;
   vector<int> ans;
   for(int i=0;i<arr.size();i++){
      if(arr[i]<LOW)q1.push(arr[i]);
      else if(arr[i]>=LOW && arr[i]<=HIGH)q2.push(arr[i]);
      else q3.push(arr[i]);
   }
   while(!q1.empty()){
      ans.push_back(q1.front());
      q1.pop();
   }
   while(!q2.empty()){
      ans.push_back(q2.front());
      q2.pop();
   }
   while(!q3.empty()){
      ans.push_back(q3.front());
      q3.pop();
   }
   return ans;
}
int main(){
   vector<int> arr = {4,3,3,5,6,3,100,321,45,54,5,6,1,2,3};
   int LOW = 5 , HIGH=10;
   vector<int> ans = ThreeWayPartition(arr,LOW,HIGH);
   for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
   cout<<'\n';
}

输出

4 3 3 3 1 2 3 5 6 5 6 100 321 45 54 

时间复杂度 - O(N)，其中N是数组的大小

空间复杂度 - O(N)，用于存储数组的元素