给定索引i，j（j> = i）如何在子阵列（i，j）上找到A [j]的频率？

给定一个整数数组A，我试图找出在给定的位置j，从A的每一个i = 0到i = j出现了多少次A [j]。我已经设计了一个如下的解决方案，如下所示：给定索引i，j（j> = i）如何在子阵列（i，j）上找到A [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]]; 
}

比我可以在logn时间回答每个查询。但是这个过程使用了太多的内存。有没有办法使用更少的内存来做到这一点？

更多的澄清，你可以看到这个问题我想解决http://codeforces.com/contest/190/problem/D

来源

2014-01-14 Unbound

创建与A相同尺寸的数组B和地图C。对于B[j]中的每个j，都会记录之前A[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 
}

来源

2014-01-14 10:22:33

也许我错过了一些东西，但是如果有关元素的最后信息超出了范围0 ... j，那么查询将如何执行？这对于在0 ... n范围内进行查找来说看起来非常完美，或者我可能严重缺少某些东西？ –

好，问题是要找出“在A中每个i = 0到i = j发生A [j]多少次”。所以关于0 ... j的信息就足够了。对于更复杂的查询，我会建议排名树的映射（映射键：A元素值;树键：元素的位置）。然后我们有O（log n）为每个查询和O（n）内存为整个结构。 –

没有给这太多的时间，但也许代替使用地图将所有的位置，用一个列表，其中每个元素你把这个元素的数量改变点，对此：

struct count_info 
{ 
    int index; 
    int count; 
    count_info* next; 
}; 
... 
std::map<int, count_info*> data;

，然后在该队列中查找正确的位置。你仍然需要一张地图，但在你下面只有这些指针的列表，查询时你查看地图上的A [i]，然后浏览列表，而我>索引& &下一个& &我< next->索引。当然，如果logn是必须的，那么这会失败，因为列表查找最坏。

来源

2014-01-14 10:09:20

不错，但在最坏的情况下是O（n）。但是，如果我们采用排名树而不是列表，它应该给出O（log n）解决方案。 –

是的，这个微小的修复受到O（n）的影响，好吧，一个相对容易的加法是按索引对'count_info *'进行堆排序，但是我猜想排名树本身保留了所有这些厨房内容。作者可以指定该任务的时间/内存限制。 –

给定索引i，j（j> = i）如何在子阵列（i，j）上找到A [j]的频率？

回答

相关问题