给定一个整数数组 A ,我试图找出在给定位置 j ,A[j] 从 A 中的每个 i=0 到 i=j 出现了多少次。我设计了一个如下的解决方案
map<int,int> CF[400005];
for(int i=0;i<n;++i)
{
cin>>A[i];
if(i!=0)
CF[i-1] = CF[i];
++CF[i][A[i]];
}
我可以在登录时间内回答每个查询。但这个过程使用了太多的内存。有什么方法可以使用更少的内存吗?
要获得更多说明,您可以查看我正在尝试解决的问题 http://codeforces.com/contest/190/problem/D
最佳答案
创建一个与 A
大小相同的数组 B
和一个映射 C
。对于 B[j]
中的每个 j
,跟踪 A[j]
在 j
之前出现的次数。在C
中,跟踪给定元素的最后一次出现。然后,您可以在恒定时间内回答查询,并且只需要 O(n) 内存。
抱歉我的伪 C++。
map<int,int> C;
int B[n]; // zeros
for(int i=0;i<n;++i)
{
cin >> A[i];
int prev = C[A[i]]; // let me assume it gives -1 if no element
if (pref == -1) // this is the fist occurrence of B[i]
B[i] = 1;
else // if not the first, then add previous occurrences
B[i] = B[prev] + 1
C[A[i]] = i; // keep track where the last info about A[j] is
}
关于c++ - 给定索引 i,j(j>=i) 如何找到 A[j] 在子数组(i,j) 中的频率?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21110075/