查詢子數組中不同元素的數量 · GeeksForGeeks 中文系列教程

# 查詢子數組中不同元素的數量 > 原文： [https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/](https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/) 給定大小為 n 且查詢數量為 q 的數組“ a []”。每個查詢可以用兩個整數 l 和 r 表示。您的任務是在子數組 l 至 r 中打印不同整數的數量。給出 a [i] < = 10 <sup>6</sup> **示例**： ``` Input : a[] = {1, 1, 2, 1, 3} q = 3 0 4 1 3 2 4 Output :3 2 3 In query 1, number of distinct integers in a[0...4] is 3 (1, 2, 3) In query 2, number of distinct integers in a[1..3] is 2 (1, 2) In query 3, number of distinct integers in a[2..4] is 3 (1, 2, 3) ``` 這個想法是使用[二叉索引樹](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/) 1. **步驟 1** ：取大小為 10 ^ 6 的數組 last_visit，其中 last_visit [i]持有數組 a 中數字 i 的最右邊索引。將此數組初始化為-1。 2. **步驟 2** ：按右端 r 的升序對所有查詢進行排序。 3. **步驟 3** ：在數組位[]中創建[二叉索引樹](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)。開始遍歷數組“ a”并同時查詢，并檢查 last_visit [a [i]]是否為-1。如果不是，請在 idx last_visit [a [i]]處使用值-1 更新位數組。 4. **步驟 4** ：設置 last_visit [a [i]] = i，并在 idx i 處將值 1 更新為位數組。 5. **步驟 5** ：通過查詢位數組來回答 r 等于 i 的所有查詢。在對查詢進行排序時，可以很容易地做到這一點。 ## C++ ```cpp // C++ code to find number of distinct numbers // in a subarray #include<bits/stdc++.h> using namespace std; const int MAX = 1000001; // structure to store queries struct Query { ????int l, r, idx; }; // cmp function to sort queries according to r bool cmp(Query x, Query y) { ????return x.r < y.r; } // updating the bit array void update(int idx, int val, int bit[], int n) { ????for (; idx <= n; idx += idx&-idx) ????????bit[idx] += val; } // querying the bit array int query(int idx, int bit[], int n) { ????int sum = 0; ????for (; idx>0; idx-=idx&-idx) ????????sum += bit[idx]; ????return sum; } void answeringQueries(int arr[], int n, Query queries[], int q) { ????// initialising bit array ????int bit[n+1]; ????memset(bit, 0, sizeof(bit)); ????// holds the rightmost index of any number ????// as numbers of a[i] are less than or equal to 10^6 ????int last_visit[MAX]; ????memset(last_visit, -1, sizeof(last_visit)); ????// answer for each query ????int ans[q]; ????int query_counter = 0; ????for (int i=0; i<n; i++) ????{ ????????// If last visit is not -1 update -1 at the ????????// idx equal to last_visit[arr[i]] ????????if (last_visit[arr[i]] !=-1) ????????????update (last_visit[arr[i]] + 1, -1, bit, n); ????????// Setting last_visit[arr[i]] as i and updating ????????// the bit array accordingly ????????last_visit[arr[i]] = i; ????????update(i + 1, 1, bit, n); ????????// If i is equal to r of any query? store answer ????????// for that query in ans[] ????????while (query_counter < q && queries[query_counter].r == i) ????????{ ????????????ans[queries[query_counter].idx] = ?????????????????????query(queries[query_counter].r + 1, bit, n)- ?????????????????????query(queries[query_counter].l, bit, n); ????????????query_counter++; ????????} ????} ????// print answer for each query ????for (int i=0; i<q; i++) ????????cout << ans[i] << endl; } // driver code int main() { ????int a[] = {1, 1, 2, 1, 3}; ????int n = sizeof(a)/sizeof(a[0]); ????Query queries[3]; ????queries[0].l = 0; ????queries[0].r = 4; ????queries[0].idx = 0; ????queries[1].l = 1; ????queries[1].r = 3; ????queries[1].idx = 1; ????queries[2].l = 2; ????queries[2].r = 4; ????queries[2].idx = 2; ????int q = sizeof(queries)/sizeof(queries[0]); ????sort(queries, queries+q, cmp); ????answeringQueries(a, n, queries, q); ????return 0; } ``` ## Java ```java // Java code to find number of distinct numbers? // in a subarray? import java.io.*; import java.util.*; class GFG? { ????static int MAX = 1000001; ????// structure to store queries ????static class Query? ????{ ????????int l, r, idx; ????} ????// updating the bit array ????static void update(int idx, int val,? ????????????????????????int bit[], int n)? ????{ ????????for (; idx <= n; idx += idx & -idx) ????????????bit[idx] += val; ????} ????// querying the bit array ????static int query(int idx, int bit[], int n)? ????{ ????????int sum = 0; ????????for (; idx > 0; idx -= idx & -idx) ????????????sum += bit[idx]; ????????return sum; ????} ????static void answeringQueries(int[] arr, int n,? ????????????????????????????????Query[] queries, int q) ????{ ????????// initialising bit array ????????int[] bit = new int[n + 1]; ????????Arrays.fill(bit, 0); ????????// holds the rightmost index of any number ????????// as numbers of a[i] are less than or equal to 10^6 ????????int[] last_visit = new int[MAX]; ????????Arrays.fill(last_visit, -1); ????????// answer for each query ????????int[] ans = new int[q]; ????????int query_counter = 0; ????????for (int i = 0; i < n; i++)? ????????{ ????????????// If last visit is not -1 update -1 at the ????????????// idx equal to last_visit[arr[i]] ????????????if (last_visit[arr[i]] != -1) ????????????????update(last_visit[arr[i]] + 1, -1, bit, n); ????????????// Setting last_visit[arr[i]] as i and updating ????????????// the bit array accordingly ????????????last_visit[arr[i]] = i; ????????????update(i + 1, 1, bit, n); ????????????// If i is equal to r of any query store answer ????????????// for that query in ans[] ????????????while (query_counter < q && queries[query_counter].r == i)? ????????????{ ????????????????ans[queries[query_counter].idx] =? ????????????????????????query(queries[query_counter].r + 1, bit, n) ????????????????????????- query(queries[query_counter].l, bit, n); ????????????????query_counter++; ????????????} ????????} ????????// print answer for each query ????????for (int i = 0; i < q; i++) ????????????System.out.println(ans[i]); ????} ????// Driver Code ????public static void main(String[] args)? ????{ ????????int a[] = { 1, 1, 2, 1, 3 }; ????????int n = a.length; ????????Query[] queries = new Query[3]; ????????for (int i = 0; i < 3; i++) ????????????queries[i] = new Query(); ????????queries[0].l = 0; ????????queries[0].r = 4; ????????queries[0].idx = 0; ????????queries[1].l = 1; ????????queries[1].r = 3; ????????queries[1].idx = 1; ????????queries[2].l = 2; ????????queries[2].r = 4; ????????queries[2].idx = 2; ????????int q = queries.length; ????????Arrays.sort(queries, new Comparator<Query>()? ????????{ ????????????public int compare(Query x, Query y) ????????????{ ????????????????if (x.r < y.r) ????????????????????return -1; ????????????????else if (x.r == y.r) ????????????????????return 0; ????????????????else ????????????????????return 1; ????????????} ????????}); ????????answeringQueries(a, n, queries, q); ????} } // This code is contributed by // sanjeev2552 ``` ## Python3 ```py # Python3 code to find number of? # distinct numbers in a subarray MAX = 1000001 # structure to store queries class Query: ????def __init__(self, l, r, idx): ????????self.l = l ????????self.r = r ????????self.idx = idx # updating the bit array def update(idx, val, bit, n): ????while idx <= n: ????????bit[idx] += val ????????idx += idx & -idx # querying the bit array def query(idx, bit, n): ????summ = 0 ????while idx: ????????summ += bit[idx] ????????idx -= idx & -idx ????return summ def answeringQueries(arr, n, queries, q): ????# initialising bit array ????bit = [0] * (n + 1) ????# holds the rightmost index of? ????# any number as numbers of a[i] ????# are less than or equal to 10^6 ????last_visit = [-1] * MAX ????# answer for each query ????ans = [0] * q ????query_counter = 0 ????for i in range(n): ????????# If last visit is not -1 update -1 at the ????????# idx equal to last_visit[arr[i]] ????????if last_visit[arr[i]] != -1: ????????????update(last_visit[arr[i]] + 1, -1, bit, n) ????????# Setting last_visit[arr[i]] as i and? ????????# updating the bit array accordingly ????????last_visit[arr[i]] = i ????????update(i + 1, 1, bit, n) ????????# If i is equal to r of any query store answer ????????# for that query in ans[] ????????while query_counter < q and queries[query_counter].r == i: ????????????ans[queries[query_counter].idx] = \ ????????????????????????query(queries[query_counter].r + 1, bit, n) - \ ????????????????????????query(queries[query_counter].l, bit, n) ????????????query_counter += 1 ????# print answer for each query ????for i in range(q): ????????print(ans[i]) # Driver Code if __name__ == "__main__": ????a = [1, 1, 2, 1, 3] ????n = len(a) ????queries = [Query(0, 4, 0),? ???????????????Query(1, 3, 1),? ???????????????Query(2, 4, 2)] ????q = len(queries) ????queries.sort(key = lambda x: x.r) ????answeringQueries(a, n, queries, q) # This code is contributed by # sanjeev2552 ``` **輸出**： ``` 3 2 3 ``` 如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請寫評論。