นับองค์ประกอบในสองอาร์เรย์โดยใช้ C++

สมมติว่าเรามีอาร์เรย์ที่ไม่ได้เรียงลำดับสองอาร์เรย์ arr1[] และ arr2[] งานคือนับจำนวนองค์ประกอบทั้งหมดใน arr2[] ซึ่งแต่ละองค์ประกอบของ arr1[] น้อยกว่าหรือเท่ากับองค์ประกอบที่มีอยู่ใน arr2[] อย่างไรก็ตาม องค์ประกอบในทั้งสองอาร์เรย์อาจมีค่าซ้ำกันได้

ตัวอย่างอินพุต

N = 6, M = 9
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[] และใช้วิธี Binary Search เพื่อหาองค์ประกอบของ arr1[] ที่น้อยกว่าหรือเท่ากับองค์ประกอบที่มีอยู่ใน arr2[]

• รับอินพุตขนาดของ arr1 และ arr2 เป็น 'm' และ 'n'
• รับอินพุตองค์ประกอบของอาร์เรย์
• ฟังก์ชัน countInSecond(int *arr1, int *arr2, int m, int n) รับสองอาร์เรย์และขนาดเป็นอินพุตและคืนค่าจำนวนองค์ประกอบที่มีอยู่ใน arr2[]
• จัดเรียง arr2[]
• วนลูปผ่าน arr1[] และใช้ binary search เพื่อหาองค์ประกอบเฉพาะใน 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}