ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และเราจะได้รับ aquery แบบสอบถามแต่ละรายการประกอบด้วยสองค่า (L, R) งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นจำนวนองค์ประกอบที่แตกต่างกันในอาร์เรย์ย่อย
คำอธิบายปัญหา − ในที่นี้ เราจะต้องค้นหาจำนวนรวมของจำนวนเต็มเฉพาะที่มีอยู่ในอาร์เรย์ย่อยตั้งแต่ดัชนี (L-1) ถึง (R-1)
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4] ผลลัพธ์
4
คำอธิบาย
สำหรับข้อความค้นหา 1:L =1 &R =4 เราจำเป็นต้องค้นหาจำนวนความแตกต่างจากดัชนี 0 ถึง 3 ซึ่งเท่ากับ 4
สำหรับข้อความค้นหา 2:L =2 &R =6 เราจำเป็นต้องค้นหาจำนวนองค์ประกอบที่แตกต่างจากดัชนี 1 ถึง 5 ซึ่งเท่ากับ 3
แนวทางการแก้ปัญหา
วิธีง่ายๆ ในการแก้ปัญหาแต่ละคำถามคือการสำรวจอาร์เรย์จาก L ไปยัง Rand เก็บองค์ประกอบไปยังชุด ซึ่งขนาดจะให้ผลลัพธ์ของการค้นหา เช่นเดียวกับที่เราได้กล่าวถึงในชุดที่แล้ว
วิธีที่มีประสิทธิภาพมากขึ้นในการแก้ปัญหาคือการใช้โครงสร้างข้อมูลต้นไม้ส่วน มันจะเก็บจำนวนองค์ประกอบที่แตกต่างกันสำหรับช่วงที่กำหนด
ต้นไม้ส่วน เป็นต้นไม้ชนิดพิเศษที่เก็บข้อมูลในรูปของส่วนต่างๆ
โหนดปลายสุดของต้นไม้ส่วนแสดงถึงองค์ประกอบของอาร์เรย์ และโหนดที่ไม่ใช่ใบไม้แสดงถึงเซ็กเมนต์ที่มีค่าที่ต้องการ ที่นี่จะเก็บองค์ประกอบที่แตกต่างออกไป สำหรับการนำโครงสร้างข้อมูลนี้ไปใช้ เราจะใช้ 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
