Đếm phần tử trong mảng 2: số lượng phần tử arr2 ≥ mỗi phần tử arr1 C++

Cho hai mảng không sắp xếp arr1 (size m) và arr2 (size n). Với mỗi phần tử x trong arr1, đếm số phần tử trong arr2 nhỏ hơn hoặc bằng x. Phần tử có thể trùng. Ví dụ:

Đầu vào: arr1={1,2,5,0,6,3}, arr2={0,0,1,2,1,3,4,6,8} → Đầu ra: 4 5 7 2 8 6.

Phương pháp: Sắp xếp arr2 + Tìm kiếm nhị phân

• Sắp xếp arr2 tăng dần.
• Với mỗi x trong arr1, dùng upper_bound (hoặc binary search thủ công) tìm vị trí đầu tiên > x. Số phần tử ≤ x chính là vị trí đó.

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

void countInSecond(int *arr1, int *arr2, int m, int n) {
    sort(arr2, arr2 + n);
    for (int i=0;i

Kết quả
4 5 7 2 8 6
Phức tạp O(n log n + m log n).