मान लीजिए हमारे पास दो अनसॉर्टेड सरणी arr1[] और arr2[] दी गई हैं। कार्य arr2[] में तत्वों की कुल संख्या गिनना है जिनके लिए arr1[] का प्रत्येक तत्व arr2[] में मौजूद तत्वों से कम या बराबर है। हालांकि, दोनों सरणियों में तत्व डुप्लिकेट भी हो सकते हैं।
उदाहरण के लिए,
इनपुट-1 -
N = 6 M = 7 arr1[N] = {1, 2, 5, 0, 6, 3} arr2[M] = {0, 0, 1, 2, 1, 3, 4, 6, 8}
आउटपुट -
4 5 7 2 8 6
इस प्रॉब्लम को हल करने के लिए उपयोग किया गया दृष्टिकोण
arr1[] के प्रत्येक तत्व को गिनने और जांचने के लिए कि क्या वे arr2[] में मौजूद तत्वों से कम या बराबर हैं, विचार यह है कि arr2[] को सॉर्ट करें और बाइनरी सर्च मेथड का उपयोग करके arr1[] के उस तत्व को ढूंढें जो arr2[] में मौजूद तत्व से कम या बराबर है।
arr1 और arr2 के आकार को 'm' और 'n' के रूप में इनपुट लें।
सरणी तत्वों का इनपुट लें।
एक फंक्शन countInSecond(int *arr1, int *arr2, int m, int n) दो सरणियों और उसके आकार को इनपुट के रूप में लेता है और arr2[] में मौजूद तत्व की गिनती लौटाता है।
arr2[] को सॉर्ट करें।
arr1[] पर पुनरावृति करें और arr2[] में विशेष तत्व को ढूंढने के लिए बाइनरी सर्च का उपयोग करें।
कम या बराबर तत्व की गिनती लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void countInSecond(int *nums1, int *nums2, int m, int n) {
sort(nums2, nums2 + n);
for (int i = 0; i < m; i++) {
int s = 0;
int e = n - 1;
while (s <= e) {
int mid = (s + e) / 2;
if (nums2[mid] <= nums1[i])
s = mid + 1;
else
e = mid - 1;
}
cout << e + 1 << " ";
}
}
int main() {
int m = 6;
int n = 9;
int arr1[m] = {1, 2, 5, 0, 6, 3};
int arr2[n] = {0, 0, 1, 2, 1, 3, 4, 6, 8};
countInSecond(arr1, arr2, m, n);
return 0;
}
आउटपुट
उपरोक्त कोड चलाने पर निम्न आउटपुट उत्पन्न होगा,
4 5 7 2 8 6
arr1 के सभी तत्वों की गिनती जो arr2 में उनसे कम या बराबर हैं, वे {4 5 7 2 8 6} हैं।
