1

O(n) 時間で問題を解決しようとしています。コンテナーの前面とコンテナーの背面に 2 つの前方反復子がある場合、少なくとも表示されないコンテナー内のすべての要素を削除したい <この回数 > 回。たとえば、("john"、"hello"、"one"、"yes"、"hello"、"one") などの文字列のベクトルが与えられ、出現回数が 2 回未満のすべての要素を削除したいとします。最終的なベクトルには、("hello", "one") のみが含まれます。

一般的に O(n) 時間でソートできれば (O(n) 時間で) この結果を達成できると考えていましたが、文字列、int、char、またはその他のものでそれを行うのに苦労しています（一般的に）使用されます。私はこれについて正しく考えていますか、それとも問題を解決するためのより簡単な方法はありますか?

4

4 に答える 4

2

短い答え：いいえ。比較ベースのソートにはO(n log n)時間がかかります。(これは形式的に証明できます。) 入力について何か知っている場合 (たとえば、入力が既知の範囲内でランダムに一様に分布している場合) は、バケット ソートや基数ソートなどのよく知られたアルゴリズムを使用できますO(n)。@Mooing Duck とは対照的に、O(1)時間内の並べ替えなどはありません (これは明らかです。並べ替えアルゴリズムでは、各要素に少なくとも 1 回アクセスする必要があります)。

ただし、他のいくつかのポスターが指摘しているように、問題にはソートアルゴリズムは必要ありません...

于 2013-02-20T02:32:26.167 に答える
2

はい、実際にはソートしていませんが、要素を削除しています。

1)。各単語をハッシュセットに保存します。2)。検索し、ハッシュセットにない場合にのみ追加します。

于 2013-02-20T02:20:05.427 に答える
1

ソートは必要ありません。必要なのは次のunordered_mapとおりです。

unordered_map<string, int> counter;
vector<string> newvec;
for(string &s : v) {
    if((++counter[s]) == 2) {
        newvec.push_back(s);
    }
}

これは C++11 コードであることに注意してください。(コード改善の提案をしてくれた @jogojapan に感謝します)。

于 2013-02-20T02:25:49.500 に答える
1

並べ替える必要はありません

1) 移入std::unordered_map<string,vector<int>> indexOfStrings;- O(N)

2)要素stringをvector size() < 2削除 - O(削除回数) <= O(N)

indexOfStrings- 文字列が出現するたびにインデックスを格納します。これにより、検索を必要とせずにベクターからすばやく削除できます。

于 2013-02-20T02:21:38.903 に答える