5

事前インタビューで、私は次のような質問に直面しています。

文字列が単一の空白で区切られた単語で構成されている場合、文字列に出現する回数でソートされた降順で単語を印刷します。

たとえば、「abb」の入力文字列は、次の出力を生成します。

b : 2
a : 1

まず、入力文字列が1文字の単語で構成されているのか、複数文字の単語で構成されているのかは明確ではありません。前者の場合、それは単純かもしれません。

これが私の考えです：

int c[26] = {0};
char *pIn = strIn;

while (*pIn != 0 && *pIn != ' ')
{
    ++c[*pIn];
    ++pIn;
}

/* how to sort the array c[26] and remember the original index? */

入力文字列内のすべての1文字の単語の頻度の統計を取得し、それを並べ替えることができます（QuickSortなどを使用）。しかし、カウント配列がソートされた後、後でペアで印刷できるように、カウントに関連付けられた1文字の単語を取得するにはどうすればよいですか？

map<const char *, int>入力文字列が複数文字の単語で構成されている場合は、aを使用して頻度を追跡する予定です。しかし、繰り返しになりますが、マップのキーと値のペアを並べ替える方法は？

質問はCまたはC++であり、どんな提案でも歓迎します。

ありがとう！

4

4 に答える 4

2

std::map<std::string, int>単語とその数を保存するためにaを使用します。次に、これを使用して単語を取得します。

while(std::cin >> word) {
    // increment map's count for that word
}

最後に、頻度の高い順に印刷する方法を理解する必要があります。これは演習として残しておきます。

于 2011-12-30T15:54:06.883 に答える
1

26のオプションしか必要ないと仮定するのは間違いなく間違っています。なぜなら、雇用主は複数文字の単語（そしておそらく数字さえも）を許可したいと思うからです。

これは、可変長の配列が必要になることを意味します。ベクトルを使用することを強くお勧めします。さらに良いのは、マップを使用することです。

文字列内の文字シーケンスを見つけるには、現在の位置（0から開始）と次のスペースの位置を見つけます。それがその言葉です。現在の位置をスペースに設定して、もう一度やり直してください。最後までこれを繰り返します。

マップを使用することにより、すでに単語/カウントを利用できるようになります。

応募する仕事に大学のスキルが必要な場合は、何らかのハッシュ関数を追加してマップを最適化することを強くお勧めします。しかし、質問の難しさから判断すると、そうではないと思います。

于 2011-12-30T15:56:53.563 に答える
1

C言語の場合：

私はブルートフォースで単純なアルゴが好きなので、次のようにします。

  1. 入力文字列をトークン化して、ソートされていない単語の配列を作成します。実際には、各単語を物理的に移動する必要があります（それぞれの長さが可変であるため）。そして、char *の配列が必要になると思います。これは、qsort（）の引数として使用します。

  2. qsort（）（降順）その単語の配列。（qsort（）のCOMPAR関数では、配列がソート順を取得するように、大きい単語が小さい単語であると偽ってください。）

3.a. ソートされた配列を調べて、同じ単語のサブ配列を探します。サブアレイの終わりと次のサブアレイの始まりは、私が見た最初の同一でない単語によって示されます。3.b. サブ配列の最後（またはソートされた配列の最後）に到達すると、（1）単語と（2）サブ配列内の同一の単語の数がわかります。

新しいステップ4の編集：別の配列（array2と呼びます）に、サブアレイ内の単語へのchar*とサブ配列内の同一の単語の数を保存します。

  1. ソートされた配列に単語がなくなると、完了です。印刷する時が来ました。

  2. 単語頻度によるqsort（）array2。

  3. array2を通過し、各単語とその頻度を出力します。

私はこれで終わりです！ランチに行きましょう。

于 2011-12-30T16:05:04.390 に答える
1

私の前のすべての答えは本当に答えを与えませんでした。

考えられる解決策について考えてみましょう。

コンテナ内の何かを数えるための多かれ少なかれ標準的なアプローチがあります。

std::mapaや。のような連想コンテナを使用できますstd::unordered_map。そしてここで、「キー」（この場合は単語）をカウント（この場合は特定の単語のカウント）に関連付けます。

そして幸いなことに、マップには非常に優れたインデックスがありますoperator[]。これにより、指定されたキーが検索され、見つかった場合は、値への参照が返されます。見つからない場合は、キーを使用して新しいエントリを作成し、新しいエントリへの参照を返します。したがって、どちらの場合も、カウントに使用される値への参照を取得します。そして、私たちは簡単に書くことができます：

std::unordered_map<char,int> counter{};
counter[word]++;

そして、それは本当に直感的に見えます。

この操作の後、度数分布表はすでに作成されています。キー（単語）でソートするか、std::mapまたはを使用してソートしますが、。を使用するとより高速にアクセスできますstd::unordered_map。

次に、頻度/カウントに従って並べ替えます。残念ながら、これはマップでは不可能です。

std::sortしたがって、 `` `std :: vector`````のような2番目のコンテナーを使用する必要があります。これにより、任意の述語に対してunsingを並べ替えることができます。または、std::multiset暗黙的に順序付けするようなコンテナーに値をコピーできます。その要素。

aの単語を取得するには、 aと標準の抽出演算子をstd::string使用します。大したことはありません。std::istringstream>>

また、stdコンテナにこのような長い名前をすべて書き込むため、usingキーワードを使用してエイリアス名を作成します。

この後、超コンパクトなコードを記述し、数行のコードでタスクを実行します。

#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <unordered_map>
#include <type_traits>
#include <iomanip>

// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair<std::string, unsigned int>;

// Standard approach for counter
using Counter = std::unordered_map<Pair::first_type, Pair::second_type>;

// Sorted values will be stored in a multiset
struct Comp { bool operator ()(const Pair& p1, const Pair& p2) const { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; } };
using Rank = std::multiset<Pair, Comp>;
// ------------------------------------------------------------

std::istringstream text{ " 4444 55555 1 22 4444 333 55555 333 333  4444  4444 55555  55555 55555 22 "};

int main() {

    Counter counter;
    
    // Count
    for (std::string word{}; text >> word; counter[word]++);

    // Sort
    Rank rank(counter.begin(), counter.end());

    // Output
    for (const auto& [word, count] : rank) std::cout << std::setw(15) << word << " : " << count << '\n';
}
于 2021-09-25T20:13:18.250 に答える