找到向量中相同整數的數量

Question

我有一個整數向量。我想在向量中計算相同的整數。我需要一個簡單的算法，但不使用太多的頭文件或內置函數，只需要一個簡單的算法。 非常感謝 例如：

std::v={1,1,1,2,2,3} 1:3----2:2----3:1 

Answer 1

Sort他們，再算上在以下數字的每一個變化。

可選的：所述計數保存到輸出陣列。

嘗試後排序：

int count = 1; 
for(int i = 1; i < v.size(); i++) 
{ 
    if(v[i-1] == v[i]) 
    { 
     count++; 
    } 
    else 
    { 
     std::cout << v[i-1] << count << std::endl; 
     count = 0; 
    } 
} 
std::cout << v[v.size()-1] << count << std::endl; 

Answer 2

另一種解決方案是創建從int附加字典爲int。並從矢量插入數字（作爲鍵）到字典。如果號碼存在，那麼你應該增加相應給定鍵的值。

注意。這本詞典（圖）保持整數的出現次數從您矢量

缺點的方法（從你的觀點） - 你應該包括映射頭。

這樣的算法的總體複雜度爲O（N日誌N）。也許這樣的算法會比排序的使用更快。你不會使用一個額外的遍歷。而且你有結構，有關於數字發生信息

Answer 3

至少有兩種方法，最常見的解決方案運行在O（N log n）的時間，這就需要你對數組進行排序，然後遍歷它來計算最長的運行時間，如@ yd1所述。

另一種方法是使用一個散列表來生成頻數分佈表。這運行在O（n）時間（假設O（1）散列表插入和查找），但由於設置散列表和需要重新分配散列表（以及衝突等）的開銷，所以對於小的輸入向量長度而言是次優的。

你不需要#include <unordered_map>來使用散列表：你自己實現一個是本科生練習:)但是你必須做很多工作才能獲得最少的必要功能。

但是，如果能保證值的載體中的範圍是一些合適的範圍內（例如0 <= i < 256），則可以使用數組作爲地圖：

vector<int> values = ... 

int table[256] = {0}; 
for(auto i = values.begin(); i != values.end(); ++i) { 

    assert(0 <= i && i < 256); 

    table[*i]++; 
} 

然後經table迭代，以得到這些值是相同的：

for(size_t i = 0; i < 256; ++i) { 

    if(table[i] > 1) cout << i << " appeared " << table[i] << " times." << endl; 
}