Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n giá trị nguyên. Và Q truy vấn mỗi truy vấn có một số nguyên k. Nhiệm vụ của chúng tôi là tạo một chương trình để giải quyết các Truy vấn cho một số số nguyên riêng biệt trong Hậu tố.
Mô tả sự cố - Chúng ta cần giải quyết các truy vấn cho các số nguyên riêng biệt trong hậu tố. Đối với mỗi truy vấn, chúng ta cần tìm số phần tử duy nhất từ k đến n tức là đếm các phần tử duy nhất từ arr [k] đến arr [n].
Mảng được lấy là 1 được lập chỉ mục.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[ ] = {5, 1, 2, 1, 6 , 5}, n = 6, Q = 3, query = {1, 3, 4} Đầu ra
4 4 3
Giải thích
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
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề để giải quyết từng truy vấn bằng cách bắt đầu từ chỉ số k đến n. Và đếm tất cả các phần tử duy nhất của mảng và trả về số lượng của mỗi truy vấn.
Giải pháp hiệu quả
Một giải pháp hiệu quả cho vấn đề là sử dụng cấu trúc dữ liệu được tính toán trước để lưu trữ số lượng duy nhất cho chỉ mục từ (n-1) đến 0. Nó được thực hiện bằng cách sử dụng một tập hợp không có thứ tự để loại bỏ việc bổ sung các phần tử trùng lặp. Chúng tôi thậm chí có thể sử dụng một mảng bổ trợ để đếm số lần xuất hiện.
Chúng tôi sẽ thêm các phần tử của mảng vào cấu trúc dữ liệu của mình bắt đầu từ cuối cùng cho đến phần tử thứ k và sau đó tìm số phần tử trong cấu trúc dữ liệu (trong trường hợp giá trị mảng ở chỉ số thứ k).
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
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