Leetcode : Produk Tatasusunan Kecuali Diri

Masalah ini kelihatan mudah untuk diselesaikan dalam masa dan ruang linear. Masalah ini dibina berdasarkan beberapa konsep asas tatasusunan.

1. Jalur lintasan.
2. Jumlah Awalan dan Akhiran.

Syarikat yang telah bertanya perkara ini dalam temu bual pengekodan mereka ialah Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe dan banyak lagi syarikat berteknologi tinggi.

Pernyataan masalah

Memandangkan nombor tatasusunan integer, kembalikan jawapan tatasusunan supaya jawapan[i] adalah sama dengan hasil darab semua elemen nombor kecuali nombor[i].

Produk mana-mana awalan atau akhiran nombor adalah dijamin untuk dimuatkan dalam 32-bit integer.

Anda mesti menulis algoritma yang berjalan dalam masa O(n) dan tanpa menggunakan operasi bahagi.

Kes ujian#1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Kes ujian#2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Memahami masalah

Masalah ini kelihatan lebih mudah untuk diselesaikan dalam masa dan ruang linear, tetapi ia adalah rumit apabila menulis pseudokod atau pelaksanaan kod sebenar.

Ilustrasi

Mari kita lihat hasil yang diharapkan daripada tatasusunan ringkas yang mengandungi 4 elemen:

input = {1, 2, 3, 4}

Jadi, nilai pada setiap indeks ialah hasil darab semua elemen lain dalam tatasusunan kecuali nilai itu sendiri. Rajah berikut menggambarkan ini.

Berdasarkan rajah di atas, kita boleh menghasilkan formula. Untuk sebarang indeks i tertentu, kita boleh mencari nilai menggunakan hasil darab unsur dari o hingga (i - 1) campur hasil darab unsur dari (i 1) hingga (N - 1). Ini digambarkan dalam rajah berikut:

Proses pemikiran

Sebelum menulis kod pseudo, buat soalan dan tanya penemuduga.

1. Perlukah saya bimbang tentang pendua?
2. Bagaimana jika tatasusunan kosong atau mempunyai satu elemen? Apakah hasil yang dijangkakan?
3. Perlukah saya mempertimbangkan/mengabaikan nilai 0 dalam mana-mana indeks dalam tatasusunan? kerana semua nilai lain mendapat 0 kecuali indeks yang mengandungi 0.
4. Apakah kes sudut/tepi untuk masalah ini?

Setelah anda dan penemuduga telah membincangkan soalan di atas, cipta pelbagai pendekatan untuk menyelesaikan masalah tersebut.

1. Pendekatan naif/brute-force.
2. Produk semua elemen.
3. Produk Kiri dan Kanan.
4. Imbuhan awalan dan akhiran.

Pendekatan 1: Naif/Brute-force

Intuisi

Untuk menggunakan pendekatan kekerasan, kita mesti melaksanakan dua gelung untuk. Apabila indeks gelung luar sepadan dengan nilai indeks gelung dalam, kita harus melangkau produk; jika tidak, kami meneruskan produk.

Algoritma

1. Memulakan Pembolehubah:
   • N = nums.length (panjang tatasusunan input).
   • hasil = new int[N] (tatasusunan untuk menyimpan hasil).
2. Gelung Luar (Lelar melalui setiap elemen dalam nombor):
   • Untuk i = 0 hingga N-1:Memulakan semasaProduk = 1.
3. Gelung Dalam (Kira produk untuk elemen semasa), untuk j = 0 hingga N-1:
   • Jika i == j, langkau lelaran semasa menggunakan continue.
   • DarabkanProduk semasa dengan nombor[j].
   • TetapkanProduk semasa kepada hasil[i].
4. Pulangan hasil.

Kod

// brute force
static int[] bruteForce(int[] nums) {
    int N = nums.length;
    int[] result = new int[N];

    for (int i = 0; i < N; i++) {
        int currentProduct = 1;
        for (int j = 0; j < N; j++) {
            if (i == j) {
                continue;
            }
            currentProduct *= nums[j];
        }
        result[i] = currentProduct;
    }
    return result;
}

Analisis kerumitan

1. Kerumitan masa: O(n^2), untuk mengulang tatasusunan dua kali dalam gelung luar dan dalam.
2. Kerumitan ruang: O(n), untuk ruang tambahan (tatasusunan hasil[]) yang kami gunakan.

Pendekatan 2: Produk tatasusunan ❌

Satu cara yang difikirkan oleh kebanyakan pembangun ialah menjalankan jumlah produk bagi semua elemen, membahagikan jumlah produk dengan setiap nilai tatasusunan dan mengembalikan hasilnya.

Pseudokod

// O(n) time and O(1) space
p = 1
for i -> 0 to A[i]
  p * = A[i]
for i -> 0 to (N - 1)
  A[i] = p/A[i] // if A[i] == 0 ? BAM error‼️  

Kod

// code implementation
static int[] productSum(int[] nums) {
    int product_sum = 1;
    for(int num: nums) {
        product_sum *= num;
    }

    for(int i = 0; i < nums.length; i++) {
        nums[i] = product_sum/nums[i];
    }
    return nums;
}

Bagaimana jika salah satu elemen tatasusunan mengandungi 0? ?

Nilai pada semua indeks kecuali indeks yang mengandungi 0 pasti akan menjadi infiniti. Selain itu, kod tersebut membuang java.lang.ArithmeticException.

Exception in thread "main" java.lang.ArithmeticException: / by zero
    at dev.ggorantala.ds.arrays.ProductOfArrayItself.productSum(ProductOfArrayItself.java:24)
    at dev.ggorantala.ds.arrays.ProductOfArrayItself.main(ProductOfArrayItself.java:14)

Pendekatan 3: Cari produk Awalan dan Akhiran

Ketahui lebih lanjut tentang jumlah awalan dan akhiran dalam Kursus Penguasaan Tatasusunan di tapak web saya https://ggorantala.dev

Intuisi & formula

Awalan dan Akhiran dikira sebelum menulis algoritma untuk hasilnya. Formula jumlah awalan dan akhiran diberikan di bawah:

Algorithm Steps

1. Create an array result of the same length as nums to store the final results.
2. Create two additional arrays prefix_sum and suffix_sum of the same length as nums.
3. Calculate Prefix Products:
   • Set the first element of prefix_sum to the first element of nums.
   • Iterate through the input array nums starting from the second element (index 1). For each index i, set prefix_sum[i] to the product of prefix_sum[i-1] and nums[i].
4. Calculate Suffix Products:
   • Set the last element of suffix_sum to the last element of nums.
   • Iterate through the input array nums starting from the second-to-last element (index nums.length - 2) to the first element. For each index i, set suffix_sum[i] to the product of suffix_sum[i+1] and nums[i].
5. Calculate the result: Iterate through the input array nums.
   • For the first element (i == 0), set result[i] to suffix_sum[i + 1].
   • For the last element (i == nums.length - 1), set result[i] to prefix_sum[i - 1].
   • For all other elements, set result[i] to the product of prefix_sum[i - 1] and suffix_sum[i + 1].
6. Return the result array containing the product of all elements except the current element for each index.

Pseudocode

Function usingPrefixSuffix(nums):
    N = length of nums
    result = new array of length N
    prefix_sum = new array of length N
    suffix_sum = new array of length N

    // Calculate prefix products
    prefix_sum[0] = nums[0]
    For i from 1 to N-1:
        prefix_sum[i] = prefix_sum[i-1] * nums[i]

    // Calculate suffix products
    suffix_sum[N-1] = nums[N-1]
    For i from N-2 to 0:
        suffix_sum[i] = suffix_sum[i+1] * nums[i]

    // Calculate result array
    For i from 0 to N-1:
        If i == 0:
            result[i] = suffix_sum[i+1]
        Else If i == N-1:
            result[i] = prefix_sum[i-1]
        Else:
            result[i] = prefix_sum[i-1] * suffix_sum[i+1]

    Return result

Code

// using prefix and suffix arrays
private static int[] usingPrefixSuffix(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];
    int[] suffix_sum = new int[nums.length];

    // prefix sum calculation
    prefix_sum[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i];
    }

    // suffix sum calculation
    suffix_sum[nums.length - 1] = nums[nums.length - 1];
    for (int i = nums.length - 2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i + 1] * nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        if (i == 0) { // when variable `i` is at 0th index
            result[i] = suffix_sum[i + 1];
        } else if (i == nums.length - 1) { // when variable `i` is at last index 
            result[i] = prefix_sum[i - 1];
        } else { // for all other indexes
            result[i] = prefix_sum[i - 1] * suffix_sum[i + 1];
        }
    }
    return result;
}

Complexity analysis

1. Time complexity: The time complexity of the given code is O(n), where n is the length of the input array nums. This is because:
   • Calculating the prefix_sum products take O(n) time.
   • Calculating the suffix_sum products take O(n) time.
   • Constructing the result array takes O(n) time.

Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).

1. Space complexity: The space complexity of the given code is O(n). This is because:
   • The prefix_sum array requires O(n) space.
   • The suffix_sum array requires O(n) space.
   • Theresult array requires O(n) space. All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n) = 3O(n), which is O(n).

Optimization ?

For the suffix array calculation, we override the input nums array instead of creating one.

private static int[] usingPrefixSuffixOptimization(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];

    // prefix sum calculation
    prefix_sum[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i];
    }

    // suffix sum calculation, in-place - `nums` array override
    for (int i = nums.length - 2; i >= 0; i--) {
        nums[i] = nums[i + 1] * nums[i];
    }

    for (int i = 0; i < nums.length; i++) {
        if (i == 0) { // when variable `i` is at 0th index
            result[i] = nums[i + 1];
        } else if (i == nums.length - 1) { // when variable `i` is at last index
            result[i] = prefix_sum[i - 1];
        } else { // for all other indexes
            result[i] = prefix_sum[i - 1] * nums[i + 1];
        }
    }
    return result;
}

Hence, we reduced the space of O(n). Time and space are not reduced, but we did a small optimization here.

Approach 4: Using Prefix and Suffix product knowledge ?

Intuition

This is a rather easy approach when we use the knowledge of prefix and suffix arrays.

For every given index i, we will calculate the product of all the numbers to the left and then multiply it by the product of all the numbers to the right. This will give us the product of all the numbers except the one at the given index i. Let's look at a formal algorithm that describes this idea more clearly.

Algorithm steps

1. Create an array result of the same length as nums to store the final results.
2. Create two additional arrays prefix_sum and suffix_sum of the same length as nums.
3. Calculate Prefix Products:
   • Set the first element of prefix_sum to 1.
   • Iterate through the input array nums starting from the second element (index 1). For each index i, set prefix_sum[i] to the product of prefix_sum[i - 1] and nums[i - 1].
4. Calculate Suffix Products:
   • Set the last element of suffix_sum to 1.
   • Iterate through the input array nums starting from the second-to-last element (index nums.length - 2) to the first element.
   • For each index i, set suffix_sum[i] to the product of suffix_sum[i + 1] and nums[i + 1].
5. Iterate through the input array nums.
   • For each index i, set result[i] to the product of prefix_sum[i] and suffix_sum[i].
6. Return the result array containing the product of all elements except the current element for each index.

Pseudocode

Function prefixSuffix1(nums):
    N = length of nums
    result = new array of length N
    prefix_sum = new array of length N
    suffix_sum = new array of length N

    // Calculate prefix products
    prefix_sum[0] = 1
    For i from 1 to N-1:
        prefix_sum[i] = prefix_sum[i-1] * nums[i-1]

    // Calculate suffix products
    suffix_sum[N-1] = 1
    For i from N-2 to 0:
        suffix_sum[i] = suffix_sum[i+1] * nums[i+1]

    // Calculate result array
    For i from 0 to N-1:
        result[i] = prefix_sum[i] * suffix_sum[i]

    Return result

Code

private static int[] prefixSuffixProducts(int[] nums) {
    int[] result = new int[nums.length];

    int[] prefix_sum = new int[nums.length];
    int[] suffix_sum = new int[nums.length];

    prefix_sum[0] = 1;
    for (int i = 1; i < nums.length; i++) {
        prefix_sum[i] = prefix_sum[i - 1] * nums[i - 1];
    }

    suffix_sum[nums.length - 1] = 1;
    for (int i = nums.length - 2; i >= 0; i--) {
        suffix_sum[i] = suffix_sum[i + 1] * nums[i + 1];
    }

    for (int i = 0; i < nums.length; i++) {
        result[i] = prefix_sum[i] * suffix_sum[i];
    }

    return result;
}

Complexity analysis

1. Time complexity: The time complexity of the given code is O(n), where n is the length of the input array nums. This is because:
   • Calculating the prefix_sum products take O(n) time.
   • Calculating the suffix_sum products take O(n) time.
   • Constructing the result array takes O(n) time.

Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).

1. Space complexity: The space complexity of the given code is O(n). This is because:
   • The prefix_sum array requires O(n) space.
   • The suffix_sum array requires O(n) space.
   • The result array requires O(n) space.

All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n) = 3O(n), which is O(n).

Approach 5: Carry Forward technique

Intuition

The carry forward technique optimizes us to solve the problem with a more efficient space complexity. Instead of using two separate arrays for prefix and suffix products, we can use the result array itself to store intermediate results and use a single pass for each direction.

Here’s how you can implement the solution using the carry-forward technique:

Algorithm Steps for Carry Forward Technique

1. Initialize Result Array:
   • Create an array result of the same length as nums to store the final results.
2. Calculate Prefix Products:
   • Initialize a variable prefixProduct to 1.
   • Iterate through the input array nums from left to right. For each index i, set result[i] to the value of prefixProduct. Update prefixProduct by multiplying it with nums[i].
3. Calculate Suffix Products and Final Result:
   • Initialize a variable suffixProduct to 1.
   • Iterate through the input array nums from right to left. For each index i, update result[i] by multiplying it with suffixProduct. Update suffixProduct by multiplying it with nums[i].
4. Return the result array containing the product of all elements except the current element for each index.

Pseudocode

prefix products
    prefixProduct = 1
    For i from 0 to N-1:
        result[i] = prefixProduct
        prefixProduct = prefixProduct * nums[i]

    // Calculate suffix products and finalize result
    suffixProduct = 1
    For i from N-1 to 0:
        result[i] = result[i] * suffixProduct
        suffixProduct = suffixProduct * nums[i]

    Return result

Code

// carry forward technique
private static int[] carryForward(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];

    // Calculate prefix products
    int prefixProduct = 1;
    for (int i = 0; i < n; i++) {
        result[i] = prefixProduct;
        prefixProduct *= nums[i];
    }

    // Calculate suffix products and finalize the result
    int suffixProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= suffixProduct;
        suffixProduct *= nums[i];
    }
    return result;
}

Explanation

1. Prefix Products Calculation:
   • We initialize prefixProduct to 1 and update each element of result with the current value of prefixProduct.
   • Update prefixProduct by multiplying it with nums[i].
2. Suffix Products Calculation:
   • We initialize suffixProduct to 1 and update each element of result(which already contains the prefix product) by multiplying it with suffixProduct.
   • Update suffixProduct by multiplying it with nums[i].

Complexity analysis

1. Time Complexity: O(n) time
2. Space Complexity: O(n) (for the result array)

This approach uses only a single extra array (result) and two variables (prefixProduct and suffixProduct), achieving efficient space utilization while maintaining O(n) time complexity.

Atas ialah kandungan terperinci Leetcode : Produk Tatasusunan Kecuali Diri. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!