Typescript コーディングクロニクル: Self を除く配列の積-jsチュートリアル-php.cn

Typescript コーディングクロニクル: Self を除く配列の積

王林

リリース： 2024-07-17 11:38:48

オリジナル

695 人が閲覧しました

Typescript Coding Chronicles: Product of Array Except Self

問題の説明:

整数配列 nums を指定すると、answer[i] が nums[i] を除く nums のすべての要素の積と等しくなるような配列の回答を返します。

nums の接頭辞または接尾辞の積は、32 ビット整数に収まることが保証されます。

除算演算を使用せずに、O(n) 時間で実行されるアルゴリズムを作成する必要があります。

例 1:

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

例 2:

入力: nums = [-1,1,0,-3,3]
出力: [0,0,9,0,0]

制約:

2
-30
nums の接頭辞または接尾辞の積は、32 ビット整数に収まることが保証されます。

フォローアップ：

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 < n; i++) {
        prefixProducts[i] = prefixProducts[i - 1] * nums[i - 1];
    }

    // Compute suffix products
    for (let i = n - 2; 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 < n; i++) {
        result[i] = prefixProducts[i] * suffixProducts[i];
    }

    return result;
}

ログイン後にコピー

時間計算量の分析:

時間計算量: O(n)、n は配列の長さです。配列を 3 回繰り返します。
空間複雑度: O(n)、プレフィックスとサフィックスの積を格納します。

制限事項:

基本的なソリューションはうまく機能しますが、プレフィックスとサフィックスの製品を保存するために余分なスペースを使用します。

最適化されたソリューション:

出力配列を使用して最初にプレフィックス製品を格納し、次にそれをインプレースで変更してサフィックス製品を含めることにより、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 < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    // Compute suffix products and multiply with the prefix products
    let suffixProduct = 1;
    for (let i = n - 1; i >= 0; i--) {
        result[i] = result[i] * suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}

ログイン後にコピー

時間計算量の分析:

時間計算量: O(n)、n は配列の長さです。配列を 2 回繰り返します。
空間複雑度: O(1)。出力配列を使用して中間結果を保存し、追加の空間を使用していないためです。

基本的なソリューションの改善点:

最適化されたソリューションは、中間結果の出力配列を使用することにより、空間の複雑さを O(1) に削減します。

エッジケースとテスト:

エッジケース:

配列にはゼロが含まれています。
配列には負の数値が含まれています。
配列の長さは最小値 (2) または最大値 (10^5) の制限です。

テストケース:

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]

ログイン後にコピー