Giả sử rằng chúng ta đã cho hai mảng không được sắp xếp arr1 [] và arr2 []. Nhiệm vụ là đếm tổng số phần tử trong arr2 [] mà mỗi phần tử của arr1 [] nhỏ hơn hoặc bằng các phần tử có trong arr2 []. Tuy nhiên, phần tử trong cả hai mảng cũng có thể chứa các phần tử trùng lặp.
Ví dụ,
Đầu vào-1 -
N = 6
M = 7
arr1[N] = {1, 2, 5, 0, 6, 3}
arr2[M] = {0,0,1,2,1,3,4,6,8} Đầu ra -
4 5 7 2 8 6
Phương pháp được sử dụng để giải quyết vấn đề này
Để đếm mọi phần tử của arr1 [] và kiểm tra xem chúng nhỏ hơn hoặc bằng các phần tử trong arr2 [], ý tưởng là sắp xếp arr2 [] và sử dụng phương pháp tìm kiếm nhị phân để tìm phần tử của arr1 [] nhỏ hơn hoặc bằng phần tử có trong arr2 [].
-
Lấy kích thước đầu vào của arr1 và arr1 là ‘m’ và ‘n’.
-
Nhận đầu vào của các phần tử mảng.
-
Một hàm countInSecond (int * arr1, int * arr2, int m, int n) nhận hai mảng và kích thước của nó làm đầu vào và trả về số lượng phần tử có trong arr2 [].
-
Sắp xếp arr2 [].
-
Lặp lại arr1 [] và sử dụng tìm kiếm nhị phân để tìm phần tử cụ thể trong arr2 [].
-
Trả về số phần tử nhỏ hơn hoặc bằng.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void countInSecond(int *nums1,int *nums2,int m,int n){
sort(nums2, nums2+n);
int i=0;
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;
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
4 5 7 2 8 6
Tổng số tất cả các phần tử của arr1 nhỏ hơn hoặc bằng các phần tử trong arr2 là {4 5 7 2 8 6}.