0

最近、コーディングの問題に取り組みました。次の問題の解決策を思いつきました。

N 個の整数で構成される空でないゼロ インデックスの配列 A が与えられます。配列 A は、テープ上の数字を表します。
0 < P < N のような任意の整数 P は、このテープを 2 つの空でない部分 A[0]、A[1]、...、A[P − 1] および A[P]、A[ に分割します。 P + 1]、...、A[N − 1]。
2 つの部分の違いは次の値です: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + .. . + A[N − 1])|
つまり、最初の部分の合計と 2 番目の部分の合計の絶対差です。
たとえば、次のような配列 A を考えます。
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
このテープを 4 つの場所に分割できます。
P = 1、差 = |3 − 10| = 7
P = 2、差 = |4 − 9| = 5
P = 3、差 = |6 − 7| = 1
P = 4、差 = |10 − 3| = 7

関数を書きます: function solution(A);
これは、N 整数の空でないゼロ インデックスの配列 A が与えられると、達成できる最小の差を返します。
たとえば、次の場合:
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
上記で説明したように、関数は 1 を返す必要があります。
N は [ 2..100,000
] の範囲内の整数です。
配列 A の各要素は [−1,000..1,000] の範囲内の整数です。

複雑さ:
予想される最悪の場合の時間の複雑さは O(N) です。
予想される最悪の場合のスペースの複雑さは O(N) であり、入力ストレージを超えています (入力引数に必要なストレージは数えません)。
入力配列の要素は変更できます。


以下は、ソリューションのテストから得たフィードバックです。

正確性: small_range レンジ シーケンス、長さ = ~1,000 1.900 秒
RUNTIME ERROR テスト済みプログラムが予期せず終了
パフォーマンス: 検出された時間の複雑さ: O(N * N)

そのため、1000 前後の範囲で 1 つの実行時エラーが発生しています。そして最も重要なことは、O(n) を取得していないことです。ネストされた for ループを使用しているため、O(n * n) を取得しています。

(1) 実行時エラーを修正するにはどうすればよいですか?
(2) 同じ問題に対して O(n) アルゴリズムをどのように構築できますか? 助言がありますか？

これが私の解決策です： 

    function solution(A){
        var len = A.length;
        var diff = [];  // Array to store the differences
        var sumLeft = 0;    // Sum of array elements from index 0 to index p - 1
        var sumRight = 0;   // Sum of array elements from index p to index n - 1
        for(var p = 1; p < len; p++){
            sumLeft = 0;
            sumRight = 0;
            // Calculate sumLeft:
            for(var i = 0; i < p; i++){
                sumLeft += A[i];
            }
            // Calculate sumRight:
            for(var j = p; j < len; j++){
                sumRight += A[j];
            }
            // Calculate differences, compute absolute values, and push into diff array:
            diff.push(Math.abs(sumLeft - sumRight));
        }
        // Return the minimum of diff array by sorting it and returning the first element:
        return bubbleSort(diff)[0];
    }

    function bubbleSort(array){
        var len = array.length;
        for(var i = 0; i < len; i++){
            for(var j = i + 1; j < len; j++){
                if(array[i] > array[j]){
                    var temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
4

4 に答える 4

0

アルゴリズムの空間と時間の複雑さを改善する方法について説明します。ネストされた for ループを使用していて、反復が大幅に増加し、十分に大きな入力に対して実行時エラーが発生している可能性があることを明確に認識しています。

最初のステップは、操作の冗長性を減らすことです。ここで、 のさまざまな値に対してleftとrightの合計を繰り返し計算しますp。それはまったく必要ありません。アルゴリズムの流れの例を示します。

 Array indices -> A [0, 1, 2, 3, ....,p ,p+1, ....n-1] for a size n array

 At any point A[p] would act as a pivot as it breaks the array into two.
 For p = 1, You just take the first element i.e A[0] and the right part of the sum is
 A[1] + A[2] + .... A[n-1]

 Let S1 = A[0] and S2 = A[1] + A[2] + .... A[n-1] for p = 1
 The pivot or the break point here is A[p] i.e A[1]

 Calculate the absolute difference |S1- S2| and store it in a variable min-diff

 For p = 2, 

 S1 will simply be S1 + A[1] i.e the previous value of S1 including the last pivot 

 S2 = S2 - A[1], as we have moved on to the next element. 
 The sum of the remaining elements would not account the element we just crossed.

Formally,

S1 = S1 + A[p-1] and S2 = S2 - A[p-1]

Calculate the new difference i.e |S1 - S2| and just check 
if it is smaller than the value of our variable min-diff. 
If it is, update the value of min-diff with the present difference, 
otherwise move on to the next element.

At any value of p, S1 represents sum of left half, 
S2 represents sum of right half and 
min-diff represents the minium absolute difference till now.

このアルゴリズムの複雑さ

  1. 時間の複雑さ

    要素の合計を計算するのは、最初に A[1]+...A[n-1] を計算するときだけです。その後、配列の要素を 1 つずつトラバースします。

    したがって、配列の要素を最大で 2 回トラバースします。したがって、時間の複雑さは明らかにO(N)です

  2. スペースの複雑さ

    このアルゴリズム全体で 3 つの追加変数、つまり S1、S2、および min-diff を使用して合計を累積し、配列の p および n 要素の値とともに最小絶対差を格納します。

    したがって、このアルゴリズムのスペースの複雑さは再びO(N)になります

余談ですが、最小の差のみを出力するため、この問題の並べ替えはまったく必要ありませんが、並べ替えを行うときは常に、バブル並べ替えを使用しないでください。これは明らかに最も効率の悪い並べ替え方法です。実行時間がO(NlogN)のマージソートまたはクイックソートを使用したほうがよいでしょう

私は自分自身を説明できたことを願っています。これを単純な関数にコード化してみてください。それほど時間はかかりません。おそらく実行時エラーも修正されるはずです。

于 2014-10-07T06:52:02.700 に答える