ベクトル内の同じ整数の数を見つける

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型から追加の辞書を作成することです。そして、ベクトルから辞書に（キーとして）数字を挿入します。 numberが存在する場合、対応する指定されたキーの値を増やす必要があります。

注。この辞書（マップ）は、あなたからの整数の出現数をベクトルで保持します。

メソッドの欠点（あなたの視点から） - マップヘッダーを含める必要があります。

このアルゴリズムの全体的な複雑さはO（N log N）です。たぶんそのようなアルゴリズムは、ソートの使用より速くなります。 1回の追加トラバースは使用しません。そして、あなたは数字の出現に関する情報を持った構造を持っています

Answer 3

最も一般的な解決策はO（n log n）時間で実行され、配列をソートし、 @ yd1で説明されているように、最長の実行です。

もう1つの方法は、ハッシュテーブルを使用して頻度テーブルを生成することです。これは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; 
}