給定索引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]的頻率？

回答

相關問題