弦數我有這樣的載體獲得矢量C++
vector <string> data
data = ["this is", "data that", "is in", "this is", "vector", "vector", "vector"]
我如何得到一個載體(或二維數組),去除重複,而是具有計數每第i個項目嗎?
即
results = [("this is", 2), ("data that", 1), ("is in", 1), ("vector", 3)]
弦數我有這樣的載體獲得矢量C++
vector <string> data
data = ["this is", "data that", "is in", "this is", "vector", "vector", "vector"]
我如何得到一個載體(或二維數組),去除重複,而是具有計數每第i個項目嗎?
即
results = [("this is", 2), ("data that", 1), ("is in", 1), ("vector", 3)]
直截了當的解決辦法是,以獨特的價值觀和他們的計數積累到地圖:
std::map<std::string, std::size_t> results;
std::for_each(begin(data), end(data), [&](std::string const& s)
{
++results[s];
});
這有linearithmic(N LG n)的時間複雜度,但因爲它必須複製每個不同的字符串值,可能會相當昂貴。您也可以就地對列表進行排序,然後計算每個值的數量,如果您的移動感知實現爲std::string
,那麼該值可能會更好。
您也可以使用'std :: reference_wrapper
哈希表怎麼樣? http://en.wikipedia.org/wiki/Hash_table(複雜性O(n)) –
@MihaiTodor:只需將'std :: map'更改爲'std :: unordered_map' – Blastfurnace
Xeo,我嘗試了很多方法。即對於數據中的每個字符串s,查看數據中的其餘元素,並且針對s的每次匹配增加計數。看起來像這是O(n^2),但我正在尋找更有效的東西 – CyberShot
您可能想嘗試'std :: map'...您可以通過字符串進行索引,並將計數器增加爲需要。 'map'按鍵(這裏是字符串)排序,不能有重複。採取未排序的列表/字符串矢量並填充地圖是O(N x log2N)操作。 –
這聽起來像是一個碰撞(哈希)表給我。嘗試查找它。 –