資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++，在 O(1) 的額外空間內重新排列陣列，使得 arr[i] 變成 arr[arr[i]]
給定一個正整數型別的陣列，例如 arr[]，大小任意，陣列中的元素值必須大於 0 且小於陣列的大小。任務是重新排列陣列，使得 arr[i] 在給定的 O(1) 空間內變成 arr[arr[i]]，並列印最終結果。
讓我們看看這個的不同輸入輸出場景 -
輸入 - int arr[] = {0 3 2 1 5 4 }
輸出 - 陣列排列前：0 3 2 1 5 4 在 O(1) 的額外空間內重新排列陣列，使得 arr[i] 變成 arr[arr[i]] 是：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 在 O(1) 的額外空間內重新排列陣列，使得 arr[i] 變成 arr[arr[i]] 是：0 1
解釋 - 給定一個大小為 2 的整數陣列，陣列中所有元素的值都小於 2。現在，我們將重新排列陣列，即 arr[arr[0]] 為 1，arr[arr[1]] 為 0。所以，重新排列後的最終陣列為 0 1。
輸入 - int arr[] = {1, 0, 2, 3}
輸出 - 陣列排列前：1 0 2 3 在 O(1) 的額外空間內重新排列陣列，使得 arr[i] 變成 arr[arr[i]] 是：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)
在函式 Rearrangement(arr, size) 內部
從 i 為 0 開始迴圈，直到 i 小於 size。在迴圈內部，將 temp 設定為 arr[arr[i]] % size，並將 arr[i] 加上 temp * size。
從 i 為 0 開始迴圈，直到 i 小於 size。在迴圈內部，將 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
744 次檢視
