समस्या विवरण
इस समस्या में, हमें पूर्णांक तत्वों की एक सरणी arr[] दी गई है। हमारा कार्य समान सरणी में प्रत्येक तत्व का फ्लोर खोजने के लिए एक प्रोग्राम बनाना है। यदि किसी तत्व का फ्लोर मौजूद है, तो हम फ्लोर प्रिंट करेंगे अन्यथा -1 प्रिंट करेंगे।
सरणी में किसी तत्व का फ्लोर वह निकटतम तत्व है जो सरणी में उस तत्व से छोटा या बराबर है।
उदाहरण
इनपुट: arr[] = {3, 1, 5, 7, 8, 2}
आउटपुट: 2 -1 3 5 7 1
व्याख्या: - 3 के लिए: फ्लोर 2 है (3 से छोटा सबसे बड़ा) - 1 के लिए: कोई छोटा तत्व नहीं, इसलिए -1 - 5 के लिए: फ्लोर 3 है - 7 के लिए: फ्लोर 5 है - 8 के लिए: फ्लोर 7 है - 2 के लिए: फ्लोर 1 है
हल का दृष्टिकोण
समस्या को हल करने का एक दृष्टिकोण नेस्टेड लूप का उपयोग करना है। एक सरणी के प्रत्येक तत्व के लिए लूप और आंतरिक वाला सरणी में तत्व के फ्लोर को खोजने के लिए।
समस्या को हल करने का एक अन्य दृष्टिकोण सॉर्ट की गई सरणी को संग्रहीत करने के लिए एक अतिरिक्त सरणी का उपयोग करना है। फिर मूल सरणी पर लूप करें और बाइनरी खोज एल्गोरिदम का उपयोग करके सॉर्ट की गई सरणी में तत्व का फ्लोर खोजें।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
void printFloorEle(int arr[], int n) {
vector<int> sortedArr(arr, arr + n);
sort(sortedArr.begin(), sortedArr.end());
for (int i = 0; i < n; i++) {
// निचली_सीमा खोजें: पहला तत्व ≥ arr[i]
auto it = lower_bound(sortedArr.begin(), sortedArr.end(), arr[i]);
if (it == sortedArr.begin()) {
// सबसे छोटा तत्व
if (arr[i] == sortedArr[1]) // डुप्लिकेट हैंडलिंग
cout << arr[i];
else
cout << -1;
} else if (it != sortedArr.end() && *it == arr[i] && next(it) != sortedArr.end() && *next(it) == arr[i]) {
// डुप्लिकेट केस: फ्लोर स्वयं है
cout << arr[i];
} else {
// फ्लोर पिछला तत्व है
cout << *(it - 1);
}
cout << "\t";
}
}
int main() {
int arr[] = {3, 1, 5, 7, 8, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "दी गई सरणी के प्रत्येक तत्व का फ्लोर है: ";
printFloorEle(arr, n);
return 0;
}
आउटपुट
दी गई सरणी के प्रत्येक तत्व का फ्लोर है: 2 -1 3 5 7 1
जटिलता विश्लेषण
- समय जटिलता: O(N log N) - सॉर्टिंग + N बाइनरी खोज
- स्पेस जटिलता: O(N) - सॉर्ट की गई कॉपी के लिए
नोट
कोड डुप्लिकेट को सही ढंग से संभालता है: यदि मान कई बार आता है, तो इसका फ्लोर स्वयं होता है।
