इस लेख में, हम एक दिए गए ऐरे को k-एलिमेंट्स द्वारा दाएं घुमाने के लिए रिवर्सल एल्गोरिदम को समझेंगे, उदाहरण के लिए −
Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4 Output : { 43, 7, 3, 7, 4, 6, 2, 6 } Explanation : ऐरे के प्रत्येक एलिमेंट को 4-एलिमेंट दाएं घुमाने पर { 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; // स्टार्ट एलिमेंट को एंड एलिमेंट से स्वैप करके ऐरे को रिवर्स करना। 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; // पूरा ऐरे रिवर्स करना reverse(arr, 0, N-1); k = k%N; // 0 से k-1 तक की एलिमेंट रेंज रिवर्स करना। reverse(arr, 0, k-1); // k से अंतिम एलिमेंट तक की एलिमेंट रेंज रिवर्स करना। 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
निष्कर्ष
इस लेख में हमने रिवर्सल एल्गोरिदम का उपयोग करके ऐरे के k-एलिमेंट्स द्वारा राइट रोटेशन की समस्या पर चर्चा की। हमने चर्चा की कि रिवर्सल एल्गोरिदम क्या है और इसे इस समस्या को हल करने के लिए कैसे लागू किया जा सकता है। हमने इस समस्या को हल करने के लिए C++ कोड पर भी चर्चा की। हम इस कोड को C, Java, Python आदि किसी भी अन्य भाषा में लिख सकते हैं। आशा है कि आपको यह लेख उपयोगी लगा होगा।
