हमें एक धनात्मक पूर्णांक प्रकार सरणी दी गई है, मान लीजिए, किसी भी आकार का arr[] ऐसा है कि किसी सरणी में तत्वों का मान 0 से अधिक होना चाहिए लेकिन किसी सरणी के आकार से कम होना चाहिए। कार्य सरणी को इस तरह से पुनर्व्यवस्थित करना है कि arr[i] arr[arr[i]] केवल दिए गए O(1) स्पेस के भीतर बन जाता है और अंतिम परिणाम प्रिंट करता है।
आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -
इनपुट - 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] is 0, arr[arr[1]] 1 है, arr [गिरफ्तारी [2]] 2 है, गिरफ्तारी [गिरफ्तारी [3]] 3 है, गिरफ्तारी [गिरफ्तारी [4]] 4 है और गिरफ्तारी [गिरफ्तारी [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] is 0, arr[arr[1]] 1 है, arr [arr[2]] 2 है और arr[arr[3]] 3 है। तो, पुनर्व्यवस्था के बाद अंतिम सरणी 0 1 2 3 है।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक प्रकार के तत्वों की एक सरणी इनपुट करें और एक सरणी के आकार की गणना करें
-
व्यवस्था से पहले सरणी को प्रिंट करें और फ़ंक्शन को कॉल करें पुनर्व्यवस्था (गिरफ्तारी, आकार)
-
समारोह के अंदर पुनर्व्यवस्था (गिरफ्तारी, आकार)
-
I से 0 तक के लिए लूप प्रारंभ करें जब तक कि i आकार से कम न हो। लूप के अंदर, temp को arr[arr[i]] % size और arr[i] +=temp * size के रूप में सेट करें।
-
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