समस्या कथन
n धनात्मक पूर्णांकों और एक संख्या k की एक सरणी को देखते हुए। k से कम या उसके बराबर सभी संख्याओं को एक साथ लाने के लिए आवश्यक स्वैप की न्यूनतम संख्या ज्ञात कीजिए।
उदाहरण
यदि इनपुट ऐरे ={1, 5, 4, 7, 2, 10} और k =6 है तो 1 स्वैप की आवश्यकता है अर्थात 2 के साथ तत्व 7 को स्वैप करें।
एल्गोरिदम
- उन सभी तत्वों की गणना करें जो 'k' से कम या उसके बराबर हों। मान लें कि गिनती 'cnt' है
- लंबाई 'cnt' की विंडो के लिए दो पॉइंटर तकनीक का उपयोग करते हुए, हर बार ट्रैक करें कि इस श्रेणी में कितने तत्व 'k' से बड़े हैं। मान लें कि कुल संख्या 'आउटऑफ़रेंज' है।
- चरण 2 दोहराएं, लंबाई 'cnt' की प्रत्येक विंडो के लिए और उनमें से न्यूनतम 'आउटऑफ़रेंज' गिनें। यह अंतिम उत्तर होगा।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n, int k) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] <= k) {
++cnt;
}
}
int outOfRange = 0;
for (int i = 0; i < cnt; ++i) {
if (arr[i] > k) {
++outOfRange;
}
}
int result = outOfRange;
for (int i = 0, j = cnt; j < n; ++i, ++j) {
if (arr[i] > k) {
--outOfRange;
}
if (arr[j] > k) {
++outOfRange;
}
result = min(result, outOfRange);
}
return result;
}
int main() {
int arr[] = {1, 5, 4, 7, 2, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 6;
cout << "Minimum swaps = " << getMinSwaps(arr, n, k) <<
endl;
return 0;
} जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
आउटपुट
Minimum swaps = 1