1

文字列を解析して、一般的な空白の場所を見つけようとしています。

これが私の弦です

abc   xyz 123   456
cba 1234a 45623 say
avc  4567 bv    456

文字列はいくつあってもかまいません。上記の文字列の一般的な空白の場所を見つけることができる、c# で推奨される一般的なアルゴリズムが必要です。

たとえば、上記の文字列の一般的な場所は次のとおりです。

4, 10 ,16

すべての文字列に空白があります。

私が試みてきたアプローチには Intersect が含まれており、可能なすべてのスペースを取得し、比較して一般的なスペースを見つけようとしていますが、最適なソリューションを見つけようとしています。

4

2 に答える 2

2 
var stringList = new[] { "abc   xyz 123   456", "cba 1234a 45623 say", "avc  4567 bv    456" };
var shortest = stringList.OrderBy(s => s.Length).First();
var result = new Collection<int>();

for (int i = 0; i < shortest.Length; i++)
{
    if (stringList.All(c => c[i] == ' ')) result.Add(i+1);
}

// Test the results
foreach (var index in result)
{
    Console.WriteLine(index);
}
于 2012-07-05T03:49:19.550 に答える
2

最初の文字列の空白である一連の位置を作成します。2 番目の文字列でこれらの位置を確認し、2 番目の文字列のその位置にある文字が空白でない場合は、セットからその位置を削除します。残りの文字列について繰り返します。

別の可能性は、各文字列で空白である位置のセットを見つけてから、それらのセットの交点を見つけることです。これには、潜在的な利点が 1 つあります。これは通常、より多くの全体的な作業を行いますが、その作業の一部 (個々のセットを見つけること) は簡単に並行して実行できます。ただし、これが頻繁に勝つとは思えません (おそらく、多くのストリングと多くのコアがある場合を除きます)。あまり明白ではないかもしれませんが、セットの交差を並行して見つけることもできます。基本的には、交差のバイナリ ツリーを実行するため、最初の反復でペア間の交差を見つけ、2 番目の反復で結果のペア間の交差を見つけます。最初のイテレーションから、1 セットだけになるまで続けます。ストリングとして少なくとも多くのコアを想定すると、これにより、時間の複雑さが O(N) から O(log N) に削減されます。

于 2012-07-05T03:49:57.047 に答える