การสืบค้นจำนวนองค์ประกอบที่แตกต่างกันใน Subarray | ชุดที่ 2 ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และมี query แต่ละ query มี 2 ค่า (L, R) ภารกิจคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นจำนวนองค์ประกอบที่แตกต่างกันใน subarray

คำอธิบายปัญหา

เราต้องหาจำนวนจำนวนเต็มที่แตกต่างกันทั้งหมดที่อยู่ใน subarray จากดัชนี (L-1) ถึง (R-1)

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4]

เอาต์พุต

4

คำอธิบาย

สำหรับ query 1: L = 1 และ R = 4 เราต้องหาจำนวนองค์ประกอบที่แตกต่างกันจากดัชนี 0 ถึง 3 ซึ่งได้ 4 ค่า

สำหรับ query 2: L = 2 และ R = 6 เราต้องหาจำนวนองค์ประกอบที่แตกต่างกันจากดัชนี 1 ถึง 5 ซึ่งได้ 3 ค่า

แนวทางแก้ปัญหา

วิธีง่ายคือการวนลูปผ่านอาร์เรย์จาก L ถึง R และเก็บค่าใน Set ซึ่งขนาดของ Set จะให้ผลลัพธ์ของ query วิธีนี้ได้กล่าวถึงในชุดก่อนหน้าแล้ว

วิธีที่มีประสิทธิภาพมากกว่าคือการใช้โครงสร้างข้อมูล Segment Tree ซึ่งจะเก็บจำนวนองค์ประกอบที่แตกต่างกันสำหรับช่วงที่กำหนด

Segment Tree เป็นต้นไม้พิเศษที่เก็บข้อมูลในรูปแบบของ segments ใบไม้ (leaf nodes) แทนองค์ประกอบของอาร์เรย์ และโหนดที่ไม่ใช่ใบไม้แทน segments พร้อมค่าที่ต้องการ ที่นี่จะเก็บจำนวนองค์ประกอบที่แตกต่างกัน สำหรับการนำไปใช้ เราจะใช้ Set

ตัวอย่างโปรแกรม

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

set<int>* segmentTree;

void CreateSegmentTree(int i, int s, int e, int arr[]) {
    if (s == e) {
        segmentTree[i].insert(arr[s]);
        return;
    }
    CreateSegmentTree(2 * i, s, (s + e) / 2, arr);
    CreateSegmentTree(1 + 2 * i, 1 + (s + e) / 2, e, arr);
    segmentTree[i].insert(segmentTree[2 * i].begin(), segmentTree[2 * i].end());
    segmentTree[i].insert(segmentTree[2 * i + 1].begin(), segmentTree[2 * i + 1].end());
}

set<int> findDistSubarray(int node, int l, int r, int a, int b) {
    set<int> left, right, distinctSubarray;
    if (b < l || a > r)
        return distinctSubarray;
    if (a <= l && r <= b)
        return segmentTree[node];
    left = findDistSubarray(2 * node, l, (l + r) / 2, a, b);
    distinctSubarray.insert(left.begin(), left.end());
    right = findDistSubarray(1 + 2 * node, 1 + (l + r) / 2, r, a, b);
    return distinctSubarray;
}

int main() {
    int arr[] = {4, 6, 1, 3, 1, 6, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int query[] = {1, 4};
    int i = (int)ceil(log2(n));
    i = (2 * (pow(2, i))) - 1;
    segmentTree = new set<int>[i];
    CreateSegmentTree(1, 0, n - 1, arr);
    set<int> distCount = findDistSubarray(1, 0, n - 1, (query[0]-1), (query[1]-1));
    cout << "The number of distinct elements in the subarray is " << distCount.size();
    return 0;
}

เอาต์พุต

The number of distinct elements in the subarray is 4