[LeetCode]238. 自分以外の配列の積を解くためのアイデア

質問

長さ n (n > 1) の整数配列 nums を指定すると、出力配列 Output が返されます。ここで、output[i] は、nums[i] を除く nums の残りの要素の積に等しくなります。

例:

入力: [1,2,3,4]
出力: [24,12,8,6]

ヒント: 質問データは、質問データのすべての要素のすべてのプレフィックス要素を保証します。 array サフィックス (または配列全体) の積は、32 ビット整数の範囲内にあります。

指示: 除算を使用せず、この問題を O(n) 時間以内に完了してください。

上級: 一定の空間複雑さ内でこの問題を完了できますか? (空間複雑性分析の目的では、出力配列は余分な空間とはみなされません。)

解決策

質問を受けたときの最初のアイデアは、for ループが 2 つ、積が 1 つ、除算が 1 つということでした。しかし、後で分かったのですが、説明書には割り算を使用しないようにと書かれていたため、他の方法を使用する必要がありました。

自分以外の累積乗算を計算しているので、現在位置を分割点として、左側の要素の積と右側の要素の積をそれぞれ計算して乗算することができます。

これには次の解決策があります:

アルゴリズム 1 (LeetCode 公式ソリューションから抜粋):

2 つの空の配列 L と R を初期化します。特定のインデックス i について、L[i] は i の左側にあるすべての数値の積を表し、R[i] は i の右側にあるすべての数値の積を表します。

L 配列と R 配列の値を埋めるには 2 つのループを使用する必要があります。配列 L の場合、最初の要素の左側に要素がないため、L[0] は 1 になるはずです。他の要素の場合:

L[i] = L[i-1] * nums[i-1]。

同様に、配列

R の場合、R[length-1] は 1 である必要があります。長さは入力配列のサイズを指します。その他の要素: R[i] = R[i+1] * nums[i+1]。

R 配列と L 配列が満たされたら、入力配列を反復処理するだけでよく、インデックス i の値は次のようになります:

L[i] * R[i]。

class Solution {
    public int[] productExceptSelf(int[] nums) {
  int arrLen = nums.length;
  int[] leftNums = new int[arrLen];
  int[] rightNums = new int[arrLen];
  leftNums[0] = 1;rightNums[arrLen-1] = 1;
  
  for(int i = 1; i < arrLen; i++){
   leftNums[i] = leftNums[i-1] * nums[i-1];
   rightNums[arrLen-i-1] = rightNums[arrLen-i] * nums[arrLen-i];
  }
  
  for(int i = 0; i < arrLen; i++){
   leftNums[i] *= rightNums[i];
  }
  
  return leftNums;
 }
}

複雑度分析

時間計算量: O(N)、ここで、N は配列 nums のサイズを指します。 L 配列と R 配列の前処理と最終的な走査計算はどちらも O(N) 時間の複雑さです。

空間複雑度: O(N)、N は配列 nums のサイズを指します。 L 配列と R 配列は、答えを作成するために使用されます。L 配列と R 配列の長さは、配列 nums のサイズです。

アルゴリズム 2: 共有配列法

全体的なアイデアは、公式の問題解決アイデアと同じです:

左の乗算 * 右の乗算。

戻り配列

returnNums を定義し、左端と右端からデータを埋めながら共有配列として扱います。次に、左端と右端の積を格納し、ループで更新する left,right を定義します。

1. 2 つのポインターが出会う前に、単に配列を埋めるだけです。

2. 2 つのポインターが相互作用する場合 (奇数の長さでのみ発生します)、埋められる値は

   left*right です。

3. 2 つが一致したら、配列の値に最終値を入力する必要があります。左側の積が左側の部分に格納されており、右側の積が計算されようとしているためです。右側の部分に格納されており、左側の製品が取得されようとしています。したがって、それらを直接乗算するだけです。

   returnNums[i] = 左 および returnNums[j] = 右。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int arrLen = nums.length;
        int[] returnNums = new int[arrLen];
        int left = 1, right = 1;    // 临时存储
        returnNums[0] = 1; returnNums[arrLen-1] = 1;
        for(int i = 1, j = arrLen-2; i < arrLen; i++, j--){
            left *= nums[i-1];
            right *= nums[j+1];
            if(i < j){  // 两指针为交会
                returnNums[i] = left;
                returnNums[j] = right;
            }else if(i == j){   // 两指针重合，奇数位情况下发生
                returnNums[i] = left*right;
            }else{              // 两指针错位
                returnNums[i] *= left;
                returnNums[j] *= right;
            }
        }
        return returnNums;
    }
}

複雑度分析

時間計算量: O(N)、前の問題解決方法と同じ、長さNのループが実行され、その時間計算量はO( N ）。

スペースの複雑さ: O(1)。タイトルで述べたように、返された配列のスペースはカウントされないため、使用される追加のストレージスペースは左右になります。したがって、一定レベルの空間複雑性のみが存在します。

以上が[LeetCode]238. 自分以外の配列の積を解くためのアイデアの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。