-4

目的は、配列a3b5c2をaaabbbbbccインプレースに変換することです。私には解決策があります：

  • 配列のサイズが無限であると仮定すると、
  • 配列を最後から解析します。
  • 番号を探す（たとえばn）
  • 何桁になるかによって、次の文字を探します。
  • それを取得したら、要素を現在の位置から配列の最後まで位置ごとに移動しますn-1。
  • 開いた位置を遭遇した文字で埋めます。

このソリューションの複雑さはO（n ^ 2）になります。O（n ^ 2）未満の複雑さのソリューションはありますか？

4

1 に答える 1

3

配列を1回解析すると、すべての数値を合計することで、最後の要素がどこにあるかを知ることができます。

一度解析して、最終的なサイズを見つけます。

それを行ったら、「終わり」から（最終的な値がどこから）それを埋め始めます：2回c、次に5回b...

これはO(n)インプレースソリューションです。

編集：

srbh.kmrがコメントで述べたように、配列に一連の不適切に配置された文字が1回だけ繰り返されている場合、これは機能しません。たとえば、配列がある場合、a1b1c1d1e7上記の答えは最後の文字を消去します。

問題を引き起こす唯一の数はです1、そして私たちはそれをで扱うことができますO(n)：

上で説明したようにアレイを処理する前に、それらを削除してください。最初から配列を解析し、aが見つかるたび1にそれを消去して、残りの文字を前方に移動します（残りの配列全体ではなく、次の文字だけ）。配列に複数1のが見つかった場合、配列の最初の部分と2番目の部分の間の穴が大きくなります。上記の配列例の場合、手順は次のようになります。

a1b1c1d1e7
// First parse gives length = 1+1+1+1+7

// Repair ones
a b1c1d1e7
ab 1c1d1e7
ab  c1d1e7
abc  1d1e7
abc   d1e7
abcd   1e7
abcd    e7
abcde    7
abcde7

次に、上記のアルゴリズムを適用します。文字の後に数字が見つからない場合は、文字を配列の最後の位置にコピーするだけです。

// Fill final array
abcde7    x
          ^ 11th position
abcde     e
abcde    ee
abcde   eee
abcde  eeee
abcde eeeee
abcdeeeeeee
abcdeeeeeee  // Here we overwrite the first "e"
abcdeeeeeee  // Then we see there are lone letters (4 times), so we leave them.
于 2012-11-20T21:57:23.157 に答える