2012-12-06 50 views
0

我的排列是唯一的數字對。我需要查看一個列表並計算給定排列發生的次數。所以我需要將它記錄在數據結構中。什麼是存儲排列的良好數據結構,以及排列發生的次數是多少?

(1,1) 0 
(1,2) 5 
(1,3) 3 
(2,2) 5 
(2,3) 2 
(3,3) 1 

最終,我需要能夠按降序排列此容器,以便我可以獲得發生最大次數的排列。 非常感謝!

+0

這些對是否存儲在一個std :: pair對象中? –

+1

什麼?置換髮生一次,否則它不是置換。 –

+0

這是一個*附近*副本:http://stackoverflow.com/q/10200806/179910,我對這個問題的回答也適用於這裏,如果從'int'到'std'的鍵類型稍作調整::對'。 –

回答

0

使用std::map<std::pair<int, int>, int>。像這樣插入:

std::map<std::pair<int, int>, int> myMap; 
typedef std::map<std::pair<int, int>, int>::iterator Iterator; 
// Insert "permutation" (0,1) with a default of 0 uses 
Iterator it=myMap.insert(std::make_pair(std::make_pair(0, 1), 0)).first; 
++it->second; // Increment use count - will use old count if already there 

你甚至不需要對它進行排序,你可以隨時在每次插入後記錄當前最大值!

請注意,插入中的外部對攜帶您的使用次數的默認值。如果元素尚未在地圖中,則它將被設置爲0。所以如果排列已經存在,它會找到你的地圖元素,否則它會插入它並將使用計數設置爲零。然後你只需要增加它!

+2

如果你使用的是C++ 11編譯器,你可以使用'auto'而不是** typedef ** :) – Snps

+0

是的, d使用無序的地圖而不是地圖。只是認爲我會堅持使用C++ 03,因爲這不是標籤C++ 11 – ltjax

+0

@Itjax這是我在想什麼,但我不確定它是否會適用於大型數據集?此外,我確實需要按降序排序,因爲這是一個需求,所以這不會是一個問題? – snazziii

0

我只是將一對無序映射到int(假設int是足夠的,您可能需要一個長或任意大的整數)。如果密鑰已經存在,只需遞增該值,否則將該值設置爲1

相關問題