ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และคิวรี Q แต่ละอันประกอบด้วยสององค์ประกอบ l และ r งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นสำหรับจำนวนองค์ประกอบที่แตกต่างกันในอาร์เรย์ย่อยใน C++
คำอธิบายปัญหา − สำหรับแต่ละแบบสอบถาม เราจำเป็นต้องค้นหาจำนวนเต็มที่แตกต่างกันในอาร์เรย์ย่อยโดยเริ่มจาก arr[l] ถึง arr[r]
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {5, 6, 1, 6, 5, 2, 1}
Q = 2
{{1, 4}, {0, 6}} ผลลัพธ์
3 4
คำอธิบาย
สำหรับข้อความค้นหา 1:l =1 และ r =4, subarray[1...4] ={6, 1, 6, 5}, องค์ประกอบที่แตกต่างกัน =3
สำหรับข้อความค้นหา 2 − l =0 และ r =6, subarray[0...6] ={5, 6, 1, 6, 5, 2, 1}, องค์ประกอบที่แตกต่างกัน =4
แนวทางการแก้ปัญหา
ในการแก้ปัญหา เราจะใช้โครงสร้างข้อมูลชุด ซึ่งความยาวจะให้จำนวนองค์ประกอบที่แตกต่างกันของอาร์เรย์สำหรับช่วงที่ระบุในแบบสอบถาม สำหรับแต่ละแบบสอบถาม เราจะแทรกองค์ประกอบทั้งหมดของช่วงในอาร์เรย์ไปยังชุด องค์ประกอบที่ซ้ำกันทั้งหมดของ subarray จะถูกละทิ้งและจะเก็บเฉพาะองค์ประกอบที่แตกต่างกัน ดังนั้นขนาดของชุดจะให้จำนวนองค์ประกอบที่แตกต่างกัน
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int solveQuery(int arr[], int l, int r) {
set<int> distElements;
for (int i = (r); i >= (l); 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
