0

この問題は、マスター配列 (すべての UID のリストを含む) で文字列を検索することに関するものです。2 番目の配列には、検索するすべての文字列が含まれます。

例えば：

最初の配列 (マスター リスト) には以下が含まれます。 UID1 UID2 UID3... UID99

2 番目の配列には以下が含まれます。UID3 UID144 UID50

最初の配列で一致が見つかった場合は 1 が返され、それ以外の場合は 0 が返されます。したがって、上記の例の出力は101.

これを処理する従来の方法はn^2!!!

4

4 に答える 4

1

マスター文字列配列をソートし、二分探索を行います。

于 2013-11-01T10:08:19.643 に答える
0

もう 1 つのオプションは、マスター リスト内の文字列のハッシュを作成することです。これは単一の O(M) (長さが O(1) であると仮定) であり、ハッシュが均等に分散されていると仮定すると、単一の要素の検索には平均 O が必要です。 (M/S)、S はハッシュのサイズです (均等な分布とは、平均して、これが同じハッシュ エントリにマッピングされる要素の量であることを意味します)。サイズをさらに制御して、スペースと効率のトレードオフを微調整できます

于 2013-11-01T10:30:10.903 に答える
0

何に関して効率的ですか？

まともな実行速度、低いメモリ使用量、および非常に (非常に!) 実装の複雑さが低い間の適切な妥協点として、@Trying の提案を使用します。

を使用qsort()して最初のマスター配列をその場で並べ替え、次に を使用bsearch()して検索します。

マスター配列にn 個の要素があり、2 番目の配列にm個の要素があると仮定すると、これは O( m *log n ) 時間の複雑さを与えるはずです。

于 2013-11-01T10:13:10.183 に答える
0

この問題には、主に次の 2 つの適切なアプローチがあります。

  • 二分検索を使用します。二分検索では、最初の配列の UID をソートする必要があり、マスター配列の要素数がO(log n)どこにあるかの解を見つけることができます。n全体の複雑さは、検索する要素の数によって異なりますO(m log n)。m

  • ハッシュマップを使用する: マスター配列の要素をハッシュマップに格納し ( O(n))、2 番目の配列の要素がハッシュマップにあるかどうかを確認できます ( O(m))。全体の複雑さはO(n+m).

2 番目のアプローチの複雑さは良く見えますが、ハッシュが悪い場合は最悪のケースになる可能性があることを覚えておく必要がありますO(m*n)(ただし、その可能性は非常に低いでしょう)。また、より多くのメモリを使用し、操作も遅くなります。あなたの場合、私は最初のアプローチを使用します。

于 2013-11-02T14:26:37.890 に答える