ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของค่าจำนวนเต็ม n ค่า และ Q เคียวรีแต่ละตัวมีจำนวนเต็ม k งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นสำหรับจำนวนเต็มที่แตกต่างกันในส่วนต่อท้าย
คำอธิบายปัญหา − เราจำเป็นต้องแก้แบบสอบถามสำหรับจำนวนเต็มที่แตกต่างกันในส่วนต่อท้าย สำหรับแต่ละข้อความค้นหา เราจำเป็นต้องค้นหาจำนวนองค์ประกอบที่ไม่ซ้ำตั้งแต่ k ถึง n เช่น นับองค์ประกอบที่ไม่ซ้ำจาก arr[k] ถึง arr[n]
อาร์เรย์ที่รับคือ 1 ดัชนี
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[ ] = {5, 1, 2, 1, 6 , 5}, n = 6, Q = 3, query = {1, 3, 4} ผลลัพธ์
4 4 3
คำอธิบาย
For Query 1: k = 1, N = 6, Count of elements from arr[1] to arr[6]. Count = 4. For Query 2: k = 3, N = 6, Count of elements from arr[3] to arr[6]. Count = 4 For Query 3: k = 4, N = 6, Count of elements from arr[4] to arr[6]. Count = 3
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายในการแก้ปัญหาแต่ละคำถามโดยเริ่มจากดัชนี k ถึง n และนับองค์ประกอบที่ไม่ซ้ำทั้งหมดของอาร์เรย์และส่งคืนจำนวนการสืบค้นแต่ละครั้ง
วิธีแก้ปัญหาที่มีประสิทธิภาพ
วิธีแก้ปัญหาที่มีประสิทธิภาพคือการใช้โครงสร้างข้อมูลที่คำนวณล่วงหน้าซึ่งเก็บจำนวนเฉพาะสำหรับดัชนีจาก (n-1) ถึง 0 ซึ่งทำได้โดยใช้ชุดที่ไม่เรียงลำดับเพื่อกำจัดการเพิ่มองค์ประกอบที่ซ้ำกัน เรายังสามารถใช้อาร์เรย์เสริมสำหรับการนับเหตุการณ์ได้อีกด้วย
เราจะเพิ่มองค์ประกอบของอาร์เรย์ลงในโครงสร้างข้อมูลของเราโดยเริ่มจากองค์ประกอบสุดท้ายจนถึงองค์ประกอบที่ k แล้วจึงหาจำนวนองค์ประกอบในโครงสร้างข้อมูล (ในกรณีของค่าอาร์เรย์ที่ดัชนี k)
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
unordered_set<int> uniqueInts;
int distIntCount[n + 1];
for (int i = n - 1; i >= 0; i--) {
uniqueInts.insert(arr[i]);
distIntCount[i + 1] = uniqueInts.size();
}
for (int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": the number of distinct integers in Suffix is "<<distIntCount[queries[i]]<<endl;
}
int main() {
int n = 6, Q = 3;
int arr[n] = {5, 1, 2, 1, 6, 5};
int queries[Q] = {1, 3, 4};
solveQueries_DistInt(n, arr, Q, queries);
return 0;
} ผลลัพธ์
For Query 1: the number of distinct integers in Suffix is 4 For Query 2: the number of distinct integers in Suffix is 4 For Query 3: the number of distinct integers in Suffix is 3
