Truy vấn số phần tử riêng biệt trong một mảng con trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n. Và Q truy vấn, mỗi truy vấn bao gồm hai phần tử l và r. Nhiệm vụ của chúng ta là tạo một chương trình giải các Truy vấn cho số phần tử khác nhau trong một mảng con trong C ++.

Mô tả sự cố - Ở đây với mỗi querry, chúng ta cần tìm tổng số các số nguyên riêng biệt trong mảng con bắt đầu từ arr [l] đến arr [r].

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

3
4

Giải thích

Đối với querry 1:l =1 và r =4, mảng con [1 ... 4] ={6, 1, 6, 5}, phần tử riêng biệt =3.

Đối với querry 2 - l =0 và r =6, mảng con [0 ... 6] ={5, 6, 1, 6, 5, 2, 1}, phần tử riêng biệt =4.

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta sẽ sử dụng cấu trúc dữ liệu tập hợp, mà độ dài của nó sẽ cung cấp cho số lượng các phần tử riêng biệt của mảng cho phạm vi được cho trong quả mọng. Đối với mỗi quả mọng, chúng tôi sẽ chèn tất cả các phần tử của phạm vi trong mảng vào tập hợp. Tất cả các phần tử trùng lặp của mảng con sẽ bị loại bỏ và chỉ các phần tử riêng biệt mới được lưu trữ, do đó kích thước của tập hợp sẽ cung cấp số lượng phần tử riêng biệt sau đó.

Progam để 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;

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;
}

Đầu ra

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