在C++中，使用O(1)額外空間重新排列數組，使正負項交替出現

我們得到一個包含正數和負數的整數型別數組，比方說，任意給定大小的 arr[] 。任務是重新排列一個數組，使得正數被負數包圍。如果有更多的積極和 負數將被排列在數組的末尾。

讓我們來看看不同的輸入輸出情況−

輸入 − int arr[] = {-1, -2, -3, 1, 2, 3 }

輸出 − 排列前的陣列：-1 -2 -3 1 2 3 重新排列一個數組，使正負項交替出現，並且不需要額外的空間是：-1 1 -2 2 -3 3。

解釋：給定一個大小為6的整數數組，其中包含正負元素。現在，我們將重新排列數組，使所有正元素都出現在負元素之前，且不需要額外的空間 被負元素和所有額外元素所包圍，最終數組的末尾將添加-1 1 -2 2 -3 3，即為最終結果。

輸入 - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};

輸出 - 排列前的陣列：-1 -2 -3 1 2 3 5 5 -5 3 1 1 將陣列依交替正負項重新排列，不使用額外空間的時間複雜度為O(1)：-1 1 -2 2 -3 3 -5 5 5 3 1 1

#解釋 - 我們給出一個大小為12的整數數組，包含正負元素。現在，我們將按照這樣的方式重新排列數組，使得所有正元素被負元素包圍，並將所有額外的元素添加到數組的末尾，即-1 1 -2 2 -3 3 -5 5 5 3 1 1將是最終結果。

下面程式中使用的方法如下

• 輸入整數類型的陣列並計算陣列的大小。

• 使用FOR循環列印執行重新排列作業之前的陣列。

• 透過傳遞陣列和陣列大小作為參數呼叫函數Rearrangement(arr, size)。

• 在函數Rearrangement(arr, size)內部

  • 宣告一個整數變數'ptr'並將其初始化為-1。

  • 從i到0的循環，直到i小於size。在循環內部，檢查如果ptr大於0，然後檢查如果arr[i]大於0且arr[ptr]小於0或arr[i]小於0且arr[ptr]大於0，則呼叫函數move_array(arr, size, ptr, i)，並檢查如果i - ptr大於2，則將ptr設為ptr 2。否則，將ptr設定為-1。

  • 檢查如果ptr等於-1，則檢查arr[i]大於0且!(i & 0x01)或(arr[i]小於0)且(i & 0x01)，然後將ptr設定為i。

• 在函數move_array(int arr[], int size, int ptr, int temp)內部

  • #聲明一個名為'ch'的字元類型變量，並將其設定為arr[temp]。

  • 從i到temp的循環，直到i大於ptr。在循環內部，將arr[i]設定為arr[i - 1]。

  • 將arr[ptr]設定為ch。

範例

#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
   char ch = arr[temp];
   for(int i = temp; i > ptr; i--){
      arr[i] = arr[i - 1];
   }
   arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
   int ptr = -1;
   for(int i = 0; i < size; i++){
      if (ptr >= 0){
         if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
            move_array(arr, size, ptr, i);
            if(i - ptr >= 2){
               ptr = ptr + 2;
            }
            else{
               ptr = -1;
            }
         }
      }
      if(ptr == -1){
         if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
            ptr = i;
         }
      }
   }
}
int main(){
   //input an array
   int arr[] = {-1, -2, -3, 1, 2, 3};
   int size = sizeof(arr) / sizeof(arr[0]);
   //print the original Array
   cout<<"Array before Arrangement: ";
   for (int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

輸出

如果我們執行上面的程式碼，它將產生以下輸出

Array before Arrangement: -1 -2 -3 1 2 3
Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3

以上是在C++中，使用O(1)額外空間重新排列數組，使正負項交替出現的詳細內容。更多資訊請關注PHP中文網其他相關文章！