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

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

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

สำหรับแต่ละ query เราต้องหาจำนวนจำนวนเต็มที่แตกต่างกันทั้งหมดใน subarray เริ่มจาก arr[l] ถึง arr[r]

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

อินพุต

arr[] = {5, 6, 1, 6, 5, 2, 1}
Q = 2
{{1, 4}, {0, 6}}

เอาต์พุต

3 4

คำอธิบาย

Query 1: l = 1 และ r = 4, subarray[1...4] = {6, 1, 6, 5}, องค์ประกอบที่แตกต่างกัน = 3

Query 2: l = 0 และ r = 6, subarray[0...6] = {5, 6, 1, 6, 5, 2, 1}, องค์ประกอบที่แตกต่างกัน = 4

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

เพื่อแก้ปัญหานี้ เราจะใช้โครงสร้างข้อมูล Set ซึ่งความยาวของมันจะให้จำนวนองค์ประกอบที่แตกต่างกันของอาร์เรย์สำหรับช่วงที่กำหนดใน query สำหรับแต่ละ query เราจะนำองค์ประกอบทั้งหมดในช่วงของอาร์เรย์ใส่เข้าไปใน Set องค์ประกอบซ้ำจะถูกทิ้ง และเหลือเฉพาะองค์ประกอบที่แตกต่างกัน ดังนั้นขนาดของ Set จะให้จำนวนองค์ประกอบที่แตกต่างกัน

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

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

int solveQuery(int arr[], int l, int r) {
    set<int> distElements;
    for (int i = l; i <= r; i++)
        distElements.insert(arr[i]);
    return distElements.size();
}

int main() {
    int arr[] = {5, 6, 1, 6, 5, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int Q = 2;
    int query[Q][2] = {{1, 4}, {0,6}};
    for(int i = 0; i < Q; i++)
        cout << "For Query " << (i+1) << ": The number of distinct elements in subarray is " << solveQuery(arr, query[i][0], query[i][1]) << "\n";
    return 0;
}

เอาต์พุต

For Query 1: The number of distinct elements in subarray is 3
For Query 2: The number of distinct elements in subarray is 4