不改變相對順序的陣列三向分割槽

---

在本文中，我們將對包含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)，用於儲存陣列的元素