4

整数 (正と負) の配列が与えられ、それぞれが最大で K ビット (および符号ビット) を持ち、配列内のすべての整数の合計も最大で K ビット (および符号ビット) を持つことが知られています。 . 配列内の整数の合計を計算するアルゴリズムを設計し、すべての中間合計も最大で K ビット (および符号ビット) を持ちます。[ヒント: 正の数と負の数を追加する順序を見つけてください]。

これは宿題ではなくインタビュー資料からの質問です

私は実際に、正と負の2つの別々の配列を作成し、両方を並べ替えてから、両方を追加して、ほとんどの負がほとんどの正に追加されるようにすることを考えています...しかし、これにはO(nlogn)時間の複雑さがあるようです(to sort) および O(n) スペースの複雑さ> 助けてください!

4

3 に答える 3

7

最初に、即時の結果をオーバーフローさせたとしても、それを表現できれば、最終的な結果は常に正しいことに注意してください。これは、任意のサイズの整数型が、Javaを含むほとんどの言語で追加されている巡回群のように機能するためです（整数オーバーフローが未定義の動作であるCや、オーバーフロー例外をスローできるC＃ではありません）。

それでもオーバーフローを防ぎたい場合は、インプレースで線形時間で実行する方法を次に示します。

  • 配列をインプレースでその負のエントリ（任意の順序）とその正のエントリ（任意の順序）に分割します。ゼロはどこにでも行き着く可能性があります。つまり、ピボットをゼロにして1つのクイックソートステップを実行します。

  • 配列niの先頭（負のエントリが配置されている場所）をポイントします。

  • pi配列の終わりを指してみましょう。
  • sumゼロにしましょう。

  • その間pi >= ni

    • sumが負の 場合
      • に追加arr[pi]しsumます。
      • がarr[pi]負（正の加数が不足している）でsum正（オーバーフローが発生している）の場合、結果はオーバーフローします。
      • デクリメントpi
    • そうしないと
      • に追加arr[ni]しsumます。
      • arr[ni]が正で負の場合sum、結果はオーバーフローします。
      • インクリメントni。

  • 最後に、ビットsum以上があるかどうかを確認します。K含まれている場合は、結果がオーバーフローすることを宣言します。

于 2013-01-27T07:42:43.280 に答える
0

オプション 1: 配列をその場で並べ替え、その半分を反復処理します。iすべてのステップで、 th 要素に th 要素を追加しsize-i-1ます。

大きな数がいくつかあるが小さな負の数が多い場合 (またはその逆) は機能しません。

オプション 2 (改善):

その場で並べ替えます。

2 つのインデックスを保持します - 1 つは最初に、もう 1 つは最後にします。彼らが会ったときにループを終了します。すべてのステップで、これまでの結果が負の場合は、2 番目のインデックスに値を追加して進めます。結果が正の場合、最初のインデックスに値を追加して進めます。

于 2013-01-27T07:14:35.183 に答える