समस्या विवरण
यहां हम देखेंगे कि सरणी को कैसे विभाजित करें, और विभाजन के बाद पहले भाग को अंतिम स्थिति में जोड़ें। मान लीजिए सरणी की सामग्री है {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}। हम इसे दो भागों में काटना चाहते हैं। पहला भाग इंडेक्स 0 से 3 तक (विभाजन आकार 4), और दूसरा भाग बाकी है। पहले भाग को अंत में जोड़ने के बाद, सरणी तत्व इस तरह होंगे: {4, 5, 6, 7, 8, 9, 0, 1, 2, 3}।
एल्गोरिदम
splitArray(arr, n, k):
begin
for i = 0 to k-1:
x := arr[0]
for j = 0 to n-2:
arr[j] := arr[j+1]
done
arr[n-1] := x
done
end
उदाहरण
#include <iostream>
using namespace std;
void splitArray(int arr[], int n, int k) {
for(int i = 0; i < k; i++) {
int x = arr[0]; // पहला नंबर लें
for(int j = 0; j <= n-2; j++) {
arr[j] = arr[j+1]; // तत्वों को बाएं शिफ्ट करें
}
arr[n-1] = x; // पहले तत्व को अंत में रखें
}
}
int main() {
int data[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(data) / sizeof(data[0]);
int k;
cout << "Enter split size: ";
cin >> k;
splitArray(data, n, k);
for(int i = 0; i < n; i++) {
cout << data[i] << " ";
}
return 0;
}
आउटपुट
Enter split size: 4 4 5 6 7 8 9 0 1 2 3
बेहतर दृष्टिकोण: std::rotate (C++11)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> data = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int k = 4;
// पहले k तत्वों को अंत में घुमाएं
rotate(data.begin(), data.begin() + k, data.end());
for (int x : data) cout << x << " ";
return 0;
}
आउटपुट
4 5 6 7 8 9 0 1 2 3
जटिलता तुलना
| विधि | समय जटिलता | स्थान जटिलता |
|---|---|---|
| नेस्टेड लूप (ऊपर) | O(k × n) | O(1) |
| std::rotate | O(n) | O(1) |
| अतिरिक्त सरणी का उपयोग | O(n) | O(n) |
व्यावहारिक अनुप्रयोग
- सर्कुलर बफर रोटेशन
- इमेज प्रोसेसिंग (पंक्ति शिफ्ट)
- डेटा ऑग्मेंटेशन
- साइफर कार्यान्वयन (कैसर सिफर)