0

私はcのハッシュテーブルの実装がかなり新しく、インタビューの質問をいくつか調べていたところ、配列内の要素の奇妙な出現を見つけることについての質問を見つけました。私はすべてをセットアップし、次のように機能しています：

int a[256]={0};
char *str="hhlloworldd";
int i;

for(i=0;i<strlen(str);++i)
    a[str[i]]++;

for(i=0;i<strlen(str);i++)
{
    if(a[str[i]]%2 == 1)
    {
        printf("Odd occurrence of %c\n",str[i]);
    }
}

私が見たハッシュテーブルソリューションの大部分（配列や文字列などの要素を数える限り）は、2つのforループを使用しています。1はそれが何であれ挿入し、1は後で結果をチェックします。これはまだO（n）の複雑さであると思います。なぜなら（間違っている場合は訂正してください）、文字列をn回通過するのはO（n）+ O（n）であり、これはO（n）に相当します。私の質問は、ハッシュテーブルに挿入するときにハッシュテーブルをチェックして、2番目のforループを削除する方法はありますか？

4

3 に答える 3

2

あなたのコードについて2つの観察があります：

  • 衝突の解決がないため、ハッシュテーブルとは何の関係もありません。
  • コードの複雑さは確かO(n)にですが、分析は正しくありません。2番目のループのタイミングは、の全体的な複雑さに対するO(256)別の言い方です。O(1)O(n)
于 2013-02-25T00:08:12.423 に答える
1

多くのコメント：

  • ハッシュテーブルは衝突を起こすことはできません。たとえば、完全なハッシュを持つハッシュテーブルは依然としてハッシュテーブルです。ハッシュテーブルの定義は、ハッシュ関数によるキーから値へのマッピングに焦点を当てています（これで定義は終わりです）。たとえば、（同一のルックアップ配列について）を参照してください。

http://c2.com/cgi/wiki?HashTable

したがって、上記は、一部の要素（文字）を値（出現回数）にマップする完全なハッシュ関数（衝突なしですべての要素をマップする）を備えたハッシュテーブルです。

  • すでにコメントしたように、strlenはΘ（n）であるため、ループの反復ごとに呼び出すと、Θ（n²）になります。strlenをループから引き出すと、これが解決されます。

  • 2番目のループはΘ（n）ですが、すでにコメントしたように、このループが一般にΘ（e）（要素の数とともに成長する）、この場合はΘ（1）である場合はより理にかなっています。とにかく、それが本当に求めているものについては、元の問題を確認してください。

  • 両方のループをマージすることはできません。これは、すべての配列要素は、文字列の最後の要素を処理した後にのみ説明できるためです。これを理解する。それが当てはまらない場合は、ハッシュ値の準備ができていると結論付けることができる初期の瞬間があります。次に、最後の要素を処理する前の瞬間を考えてみてください。最後の要素を処理していない場合は、そのうちの1つを1つインクリメントする必要があります。次に、256個のバケットのいずれかが変更された可能性があります。しかし、どれを推測する方法はありません。最後の要素を読み取る必要があります。ループの終了後、抜け出す唯一の方法は、もう一度ループすることです。

于 2013-02-25T01:01:21.090 に答える
0

あなたのコードにはバグがあるようですが、おそらく私はあなたの要件を正しく取得していませんでした：

一部の文字xが入力に奇数回出現する場合、2番目のforループは、それが表示されるたびに「奇数発生」として報告します。

2つのforループを1つにマージする必要があります。補足として、strlen（）のようなO（n）操作をループ条件に置くことは、strlenが繰り返し呼び出されないように、または2次パフォーマンスで終わるようにstrが変更されていないことをコンパイラーが理解することに依存します。

int a[256]={0};
int n = strlen(str);
int i;

for(i=0;i<n;++i)
{
    ++a[str[i]];
    if(0 != a[str[i]]%2)
    {
        printf("Odd occurrence of %c\n",str[i]);
    }
}

簡単なルックアップテーブルが機能するのにキースペースが十分に小さい場合（この場合はサイズ256）にハッシュテーブルが必要な理由がわかりません。

于 2013-02-25T00:00:35.797 に答える