คิวรีสำหรับมากกว่าและไม่น้อยกว่า โดยใช้ C++

ในบทความนี้ เราได้รับปัญหา เราได้รับอาร์เรย์ และมีสองประเภทของคิวรีที่เราต้องตอบ:

• ประเภท 0 - เราต้องคำนวณจำนวนองค์ประกอบที่มากกว่าหรือเท่ากับ x (ค่าที่กำหนด)
• ประเภท 1 - เราต้องคำนวณจำนวนองค์ประกอบที่มากกว่า x (ค่าที่กำหนด) อย่างเคร่งครัด

นี่คือตัวอย่างง่ายๆ:

Input : arr[] = { 10, 15, 30, 40, 45 } และ Q = 3
Query 1: 0 50
Query 2: 1 40
Query 3: 0 30
Output :   0   1   3
คำอธิบาย: x = 50, q = 0 : ไม่มีองค์ประกอบมากกว่าหรือเท่ากับ 50
x = 40, q = 1 : 45 มากกว่า 40
x = 30, q = 0 : สามองค์ประกอบ 30, 40, 45 มากกว่าหรือเท่ากับ 30

วิธีการแก้ปัญหา

เราสามารถใช้สองวิธีที่แตกต่างกันเพื่อหาคำตอบ แรกเราจะใช้วิธี Brute Force แล้วตรวจสอบว่ามันสามารถทำงานกับข้อจำกัดที่สูงกว่าได้หรือไม่ ถ้าไม่ได้ เราจะดำเนินการเพิ่มประสิทธิภาพวิธีแก้ปัญหาของเรา

วิธี Brute Force

ในวิธีนี้ เราจะเดินทางผ่านอาร์เรย์สำหรับคิวรีทั้งหมด q และหาตัวเลขที่ตรงตามเงื่อนไขที่กำหนด

ตัวอย่าง

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

void query(int *arr, int n, int type, int val) {
    int count = 0; // คำตอบ
    if(!type) { // เมื่อถามคิวรีประเภท 0
        for(int i = 0; i < n; i++) {
            if(arr[i] >= val)
                count++;
        }
    } else { // เมื่อถามคิวรีประเภท 1
        for(int i = 0; i < n; i++) {
            if(arr[i] > val)
                count++;
        }
    }
    cout << count << "\n";
}

int main() {
    int ARR[] = { 10, 15, 30, 40, 45 };
    int n = sizeof(ARR)/sizeof(ARR[0]); // ขนาดของอาร์เรย์
    query(ARR, n, 0, 50); // คิวรี 1
    query(ARR, n, 1, 40); // คิวรี 2
    query(ARR, n, 0, 30); // คิวรี 3
    return 0;
}

ผลลัพธ์

0 1 3

ในวิธีข้างต้น เราเพียงแค่เดินทางผ่านอาร์เรย์และคำนวณคำตอบสำหรับคิวรี วิธีนี้ทำงานสำหรับตัวอย่างที่กำหนด แต่ถ้าเราพบข้อจำกัดที่สูงกว่า วิธีนี้จะล้มเหลว เพราะความซับซ้อนด้านเวลาทั้งหมดของโปรแกรมคือ O(N×Q) โดยที่ N คือขนาดของอาร์เรย์ และ Q คือจำนวนคิวรี ดังนั้นตอนนี้เราจะเพิ่มประสิทธิภาพวิธีนี้ให้ทำงานได้กับข้อจำกัดที่สูงกว่าด้วย

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะใช้ Binary Search เพื่อหา upper bound และ lower bound ของค่าที่กำหนด เราจัดเรียงอาร์เรย์ของเราก่อนโดยใช้ binary search แล้วจึงนำฟังก์ชัน lower bound และ upper bound ไปใช้ตามลำดับ

ตัวอย่าง

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

void lowerbound(int *arr, int n, int val) {
    int l = -1, r = n;
    while(r - l > 1) { // binary search คำตอบ
        int mid = (l+r)/2;
        if(arr[mid] >= val)
            r = mid;
        else
            l = mid;
    }
    if(r == n) // ถ้า r ไม่เคลื่อนไหว หมายความว่าไม่มีองค์ประกอบที่ตรงตามเงื่อนไข
        cout << "0\n";
    else
        cout << n - r << "\n";
}

void upperbound(int *arr, int n, int val) {
    int l = -1, r = n;
    while(r - l > 1) { // binary search คำตอบ
        int mid = (l+r)/2;
        if(arr[mid] > val)
            r = mid;
        else
            l = mid;
    }
    if(r == n)// ถ้า r ไม่เคลื่อนไหว หมายความว่าไม่มีองค์ประกอบที่ตรงตามเงื่อนไข
        cout << "0\n";
    else
        cout << n - r << "\n";
}

void query(int *arr, int n, int type, int val) {
    if(!type) // ถ้า type == 0 เรียกฟังก์ชัน lower bound
        lowerbound(arr, n, val);
    else // ถ้า type == 1 เรียกฟังก์ชัน upperbound
        upperbound(arr, n, val);
}

int main() {
    int arr[] = { 1, 2, 3, 4 };
    int n = sizeof(arr)/sizeof(arr[0]); // ขนาดของอาร์เรย์
    sort(arr, arr+n); // จัดเรียงอาร์เรย์
    query(arr, n, 0, 5); // คิวรี 1
    query(arr, n, 1, 3); // คิวรี 2
    query(arr, n, 0, 3); // คิวรี 3
    return 0;
}

ผลลัพธ์

0 1 2

โค้ดข้างต้นทำงานบน binary search ที่ลดความซับซ้อนด้านเวลาลงอย่างมาก ดังนั้นความซับซ้อนสุดท้ายของเราจะกลายเป็น O(N log N) โดยที่ N คือขนาดของอาร์เรย์

คำอธิบายโค้ด

ในวิธีนี้ เราจะใช้ binary search เพื่อหา upper bound และ lower bound ของค่าที่กำหนด ตอนนี้สำหรับ binary search เราจัดเรียงอาร์เรย์ของเราก่อนเพราะมันทำงานได้เฉพาะกับอาร์เรย์ที่จัดเรียงแล้ว เราสร้างฟังก์ชัน lower bound และ upper bound ที่ช่วยให้เราหาตัวเลขแรกที่ตรงตามเงื่อนไข type 0, type 1 ตามลำดับ ตอนนี้เนื่องจากเราจัดเรียงอาร์เรย์แล้ว เราพบตัวเลขแรกที่ช่วยให้เงื่อนไขเป็นจริง ดังนั้นองค์ประกอบหลังจากองค์ประกอบนี้ก็จะทำตามเงื่อนไขเช่นกัน ดังนั้นเราพิมพ์ความแตกต่างของดัชนีขององค์ประกอบนี้กับ N (ขนาดของอาร์เรย์)

สรุป

ในบทความนี้ เราแก้ปัญหา Queries for greater than and not less than โดยใช้ Binary search เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ธรรมดาและมีประสิทธิภาพ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์