對已根據元素絕對值排序的陣列進行排序

---

在本文中，我們將對給定的陣列進行排序。給定的陣列已經根據元素的絕對值排序，我們只需要根據元素的真實值對陣列進行排序。

在第一種方法中，我們將使用排序演算法，例如歸併排序、氣泡排序、插入排序、快速排序等等。在本例中，我們將使用內建的排序函式來排序我們的陣列。

在第二種方法中，我們將使用雙端佇列。我們將正元素推入雙端佇列的前面，並將負元素推入雙端佇列的後面。這種方法允許我們無需執行任何排序演算法即可獲得排序後的陣列。

問題陳述

給定一個包含N個整數的陣列，這些整數已根據元素的絕對值排序，我們需要根據陣列中元素的真實值對陣列進行排序。

示例

輸入

arr = {1, 2, -3, -8, 16}

輸出

-8, -3, 1, 2, 16

解釋

將輸入陣列按升序排序後，負值出現在陣列的開頭，我們得到最終的輸出。

輸入

arr = {8, -8, -8, 8}

輸出

-8, -8, 8, 8

解釋

由於 -8 小於 8，因此在排序後它應該出現在 8 之前。

輸入

arr = {-2, -33, -71, 81, 93}

輸出

-71, -33, -2, 81, 93

解釋

負值在輸出中將以相反的順序出現。

方法一

在這種方法中，我們將使用排序技術對輸入陣列進行排序。我們可以使用多種排序技術，例如歸併排序、快速排序、氣泡排序、選擇排序、插入排序等等。解決方案的時間和空間複雜度將取決於所使用的排序技術的型別。在下面的示例中，我們將使用內建的排序函式來排序陣列。

演算法

• 步驟 1 − 將輸入陣列作為引數。

• 步驟 2 − 建立一個新陣列 res，並將輸入陣列的元素複製到 res 中，並保持相同的順序。

• 步驟 3 − 使用內建排序函式對新陣列 res 進行排序。

• 步驟 4 − 返回排序後的陣列。

示例

#include <bits/stdc++.h>
using namespace std;
vector<int> sort_abs_sorted(vector<int> &arr){
   vector<int> res = arr;
   sort(res.begin(),res.end());
   return res;
}
int main(){
   vector<int> arr = {-2, -33, -71, 81, 93};
   vector<int> sorted = sort_abs_sorted(arr);
   for(int i=0;i<sorted.size();i++)cout<<sorted[i]<<" ";
   return 0;
}

輸出

-71 -33 -2 81 93

時間複雜度 − O(N*log(N))，其中 N 是陣列中元素的數量。

空間複雜度 − O(N)，用於在新陣列中儲存元素

方法二

在這種方法中，我們將使用雙端佇列根據元素的真實值對陣列進行排序。首先，我們將從左到右遍歷原始陣列。如果當前元素為正，我們將元素推入佇列的後面。如果當前元素為負，我們將元素推入佇列的前面。遍歷所有元素後，我們將建立一個新的陣列來儲存排序後的元素。我們一個接一個地從雙端佇列中獲取元素並將其新增到我們的最終陣列中。

演算法

• 步驟 1 − 建立一個雙端佇列。

• 步驟 2 − 從左到右遍歷輸入陣列。

• 步驟 2.1 − 如果當前元素為正，則將其推入雙端佇列的後面。

• 步驟 2.2 − 如果當前元素為負，則將其推入佇列的前面。

• 步驟 3 − 建立一個最終陣列來儲存排序後的元素。

• 步驟 3.1 − 從雙端佇列中彈出元素並將其新增到最終陣列中。

• 步驟 3.3 − 返回排序後的陣列。

示例

#include <bits/stdc++.h>
using namespace std;
vector<int> sort_abs_sorted(vector<int> &arr){
   vector<int> res;
   deque<int> deq;
   for(int i=0;i<arr.size();i++){
      if(arr[i]>=0)deq.push_back(arr[i]);
      else deq.push_front(arr[i]);
   }
   for(auto it:deq)res.push_back(it);
   return res;
}
int main(){
   vector<int> arr = {-2, -33, -71, 81, 93};
   vector<int> sorted = sort_abs_sorted(arr);
   for(int i=0;i<sorted.size();i++)cout<<sorted[i]<<" ";
   return 0;
}

輸出

-71 -33 -2 81 93

時間複雜度 − O(N)，其中 N 是陣列中元素的數量。

空間複雜度 − O(N)，用於在佇列中儲存元素。