整数配列 nums を指定すると、answer[i] が nums[i] を除く nums のすべての要素の積と等しくなるような配列の回答を返します。
nums の接頭辞または接尾辞の積は、32 ビット整数に収まることが保証されます。
除算演算を使用せずに、O(n) 時間で実行されるアルゴリズムを作成する必要があります。
O(1) 個の余分な空間複雑さの問題を解決できますか? (出力配列は、空間複雑性分析の追加スペースとしてカウントされません。)
この問題を解決するには、除算演算を使用せずに、現在の要素を除くすべての要素の積を計算する必要があります。これは、配列
に対して 2 つのパスを使用することで実行できます。2 つの配列を使用してプレフィックスとサフィックスの積を保存し、それらを乗算して最終結果を得ることができます。
function productExceptSelf(nums: number[]): number[] { const n = nums.length; const prefixProducts = new Array(n).fill(1); const suffixProducts = new Array(n).fill(1); const result = new Array(n).fill(1); // Compute prefix products for (let i = 1; i = 0; i--) { suffixProducts[i] = suffixProducts[i 1] * nums[i 1]; } // Compute the result by multiplying prefix and suffix products for (let i = 0; i時間計算量の分析:
基本的なソリューションはうまく機能しますが、プレフィックスとサフィックスの製品を保存するために余分なスペースを使用します。
出力配列を使用して最初にプレフィックス製品を格納し、次にそれをインプレースで変更してサフィックス製品を含めることにより、O(1) 個の追加スペースを使用するようにソリューションを最適化できます。
function productExceptSelfOptimized(nums: number[]): number[] { const n = nums.length; const result = new Array(n).fill(1); // Compute prefix products in the result array for (let i = 1; i = 0; i--) { result[i] = result[i] * suffixProduct; suffixProduct *= nums[i]; } return result; }
console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6] console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0] console.log(productExceptSelf([2,2,2,2])); // [8,8,8,8] console.log(productExceptSelf([0,0])); // [0,0] console.log(productExceptSelf([5])); // This should not be a valid input as the minimum length is 2 console.log(productExceptSelf([1,2])); // [2, 1] console.log(productExceptSelfOptimized([1,2,3,4])); // [24,12,8,6] console.log(productExceptSelfOptimized([-1,1,0,-3,3])); // [0,0,9,0,0] console.log(productExceptSelfOptimized([2,2,2,2])); // [8,8,8,8] console.log(productExceptSelfOptimized([0,0])); // [0,0] console.log(productExceptSelfOptimized([5])); // This should not be a valid input as the minimum length is 2 console.log(productExceptSelfOptimized([1,2])); // [2, 1]
プレフィックス合計配列:
インプレース アルゴリズム:
配列操作:
このような問題と戦略を実践することで、問題解決スキルを向上させ、さまざまなコーディングの課題に対する準備を整えることができます。
免責事項: 提供されるすべてのリソースの一部はインターネットからのものです。お客様の著作権またはその他の権利および利益の侵害がある場合は、詳細な理由を説明し、著作権または権利および利益の証拠を提出して、電子メール [email protected] に送信してください。 できるだけ早く対応させていただきます。
Copyright© 2022 湘ICP备2022001581号-3