给定一个数组(未排序)和几个范围查询。对于每个查询,我需要找到给定范围内唯一数字的数量。这是我想出的天真的方法。
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int n; scanf("%d",&n); //Size of the array
int a[n+1]; a[0]=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int q; scanf("%d",&q); //Number of queries
while(q--)
{
int x,y; scanf("%d %d",&x,&y); //Range of each query
int bit[n+1];
for(int i=0;i<=n;i++)
bit[i]=0;
for(int i=1;i<=n;i++)
{
for(int j=i-1;j>0;j--)
{
bit[i]=a[i];
if(bit[j]==a[i])
{
bit[j]=0;
break;
}
}
}
int cnt=0;
for(int i=x;i<=y;i++)
{
if(bit[i])
cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
执行此操作最有效的方法是什么?我认为这可以使用二进制索引树来完成,但无法提出解决方案。
最佳答案
如果范围查询的数量与数组的大小相比较小,比如 O(k) vs O(n) 其中 k << n,则:
- 将所有范围端点放入平衡二叉树 O(klogk)
- 遍历数组并计算每个子范围中的唯一元素。使用哈希表来记住我们已经看到的元素。 O(n)
- 在每个范围查询的范围端点之间按顺序遍历并求和子范围总数。 O(k^2) 最坏情况/O(klogk) 合理查询。
关于arrays - 如何有效地找到数组给定范围内的唯一数字?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27996600/