इस लेख में, हम किसी दिए गए सरणी को k- तत्वों द्वारा दाईं ओर घुमाने के लिए उत्क्रमण एल्गोरिथ्म को समझेंगे, उदाहरण के लिए -
Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
Output : { 43, 7, 3, 7, 4, 6, 2, 6 }
Explanation : Rotating each element of array by 4-element to the right gives { 43, 7, 3, 7, 4, 6, 2, 6 }.
Input : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3
Output : { 4, 9, 3, 8, 5, 8, 2, 1 } समाधान खोजने के लिए दृष्टिकोण
आप प्रत्येक तत्व को दाईं ओर स्थानांतरित करके और इस प्रक्रिया को k-बार दोहराकर इस समस्या को आसानी से हल कर सकते हैं। लेकिन इसमें अधिक समय लगेगा क्योंकि इसकी समय जटिलता O(k * N) होगी।
उत्क्रमण एल्गोरिथम:उत्क्रमण एक सरणी को उलट देता है, और एक सरणी को घुमाने के लिए कुछ तत्व श्रेणी को उलट कर किया जा सकता है। इस एल्गोरिथम के अनुसार -
- सबसे पहले, पूरी सरणी को उलट दें।
- k को N (सरणी आकार) के साथ k के मापांक के साथ संशोधित करें क्योंकि k, N से बड़ा है।
- सरणी के पहले k तत्वों को क्रम में लाने के लिए उलट दें।
- फिर शेष तत्वों की श्रेणी को उलट दें, यानी k से N-1 तक।
उदाहरण
using namespace std;
#include <bits/stdc++.h>
void reverse(int nums[], int start,int end) {
int temp=0;
// reversing array with swapping start element with end element.
while(start<=end){
temp=nums[end];
nums[end]=nums[start];
nums[start]=temp;
start++;
end--;
}
}
int main() {
int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5 };
int N = sizeof(arr)/sizeof(arr[0]);
int k = 4;
// reversing whole array
reverse(arr, 0, N-1);
k = k%N;
// reversing element range of 0 to k-1.
reverse(arr, 0, k-1);
// reversing element range of k to last element.
reverse(arr, k, N-1);
cout << "Array after rotating by k-elements : ";
for(int i = 0;i<N;i++)
cout << arr[i] << " ";
return 0;
} आउटपुट
Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3
निष्कर्ष
इस लेख में हमने रिवर्सल एल्गोरिथम का उपयोग करके के-तत्वों द्वारा एक सरणी के सही रोटेशन की समस्या पर चर्चा की। हमने चर्चा की कि रिवर्सल एल्गोरिदम क्या है और इस समस्या को हल करने के लिए इसे कैसे लागू किया जा सकता है। हमने इस समस्या को हल करने के लिए C++ कोड पर भी चर्चा की। हम इस कोड को किसी अन्य भाषा जैसे C, Java, Python, आदि में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।