重新排列一個數組，使得arr變成arr]，並且只使用O(1)額外的空間，使用C++實現

我們得到一個正整數類型數組，比方說，任意給定大小的 arr[]，這樣數組中的元素值應大於 0 但小於數組的大小。任務是重新排列 一個數組，僅在給定的 O(1) 空間內將 arr[i] 變為 arr[arr[i]] 並列印最終結果。

讓我們來看看這個情況的各種輸入輸出場景−

輸入− int arr[] = {0 3 2 1 5 4 }

輸出− 排列前的陣列： 0 3 2 1 5 4 重新排列數組，使arr[i] 變成arr[arr[i]]，並具有O(1) 額外空間： 0 1 2 3 4 5

解釋#− 我們給定一個大小為6 的整數數組，並且數組中的所有元素值小於6。現在，我們將重新排列數組，即arr[arr[0] 為0，arr[arr[1]] 為1，arr[arr [2]] 為2，arr[arr[3]] 為3，arr[ arr[4]] 為4，arr[arr[5]] 為5。因此，重新排列後的最終陣列為0 1 2 3 4 5.

#輸入− int arr[] = {1, 0}

輸出− 排列前的陣列：1 0 重新排列數組，使arr[i] 變成arr[arr[i]]，其中O(1) 額外空間為： 0 1

解釋 - 我們得到一個整數大小為2 且陣列中所有元素值小於2 的陣列。現在，我們將重新排列該數組，即 arr[arr[0] 為 1，arr[arr[1]] 為 0。因此，重新排列後的最終數組是 0 1。

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

輸出−排列前的陣列：1 0 2 3 重新排列數組，使arr[i] 變成arr[arr[i]]，並具有O(1) 額外空間： 0 1 2 3

解釋 - 我們給出大小為4 的整數數組，且數組中的所有元素值小於4。現在，我們將重新排列數組，即 arr[arr[0] 為 0，arr[arr[1]] 為 1，arr[arr[2] ]] 為 2，arr[arr[3]] 為 3。因此，重新排列後的最終數組為 0 1 2 3。

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

• 輸入一個整數元素數組，計算數組大小

• 列印排列前的數組，呼叫函數Rearrangement (arr, size)

• 函數內部重排(arr, size)

  • 開始循環FOR from i 到0 直到i 小於大小。在循環內部，將 temp 設定為 arr[arr[i]] % size 和 arr[i] = temp * size。

  • 開始迴圈 FOR 從 i 到 0 直到 i小於尺寸。在循環內，設定 arr[i] = arr[i] / size

• 列印結果。

範例

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   for(int i=0; i < size; i++){
      int temp = arr[arr[i]] % size;
      arr[i] += temp * size;
   }
   for(int i = 0; i < size; i++){
      arr[i] = arr[i] / size;
   }
}
int main(){
   //input an array
   int arr[] = {0, 3, 2, 1, 5, 4};
   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 so that arr[i] becomes arr[arr[i]] with O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

輸出

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

Array before Arrangement: 0 3 2 1 5 4
Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5

#

以上是重新排列一個數組，使得arr變成arr]，並且只使用O(1)額外的空間，使用C++實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！