Leetcode : 자기를 제외한 배열의 곱

이 문제는 선형적인 시간과 공간에서 해결하기 쉬워 보입니다. 이 문제는 배열의 기본 개념 중 일부를 기반으로 합니다.

1. 배열 순회.
2. 접두사와 접미사의 합입니다.

코딩 인터뷰에서 이에 대해 질문한 회사는 Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe 및 기타 많은 최고 기술 회사입니다.

문제 진술

정수 배열 nums가 주어지면, 답변[i]가 nums[i]를 제외한 nums의 모든 요소의 곱과 동일하도록 배열 답변을 반환합니다.

nums의 접두사 또는 접미사의 곱은 32비트 정수에 맞도록 보장

됩니다.

나누기 연산을 사용하지 않고 O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

테스트 사례#1:

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

테스트 사례#2:

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

문제 이해

이 문제는 선형적인 시간과 공간에서 해결하는 것이 더 간단해 보이지만 의사 코드를 작성하거나 실제 코드 구현을 할 때는 까다롭습니다.

삽화

4개의 요소가 포함된 간단한 배열에서 예상되는 결과를 살펴보겠습니다.

input = {1, 2, 3, 4}

따라서 각 인덱스의 값은 값 자체를 제외한 배열의 다른 모든 요소의 곱입니다. 다음 그림은 이를 보여줍니다.

위의 그림을 바탕으로 공식을 생각해 볼 수 있습니다. 주어진 인덱스 i에 대해 o에서 (i - 1)까지의 요소 곱과 (i + 1)에서 (N - 1)까지의 요소 곱을 사용하여 값을 찾을 수 있습니다. 이는 다음 그림에 설명되어 있습니다.

사고 과정

의사 코드를 작성하기 전에 먼저 질문을 떠올리고 면접관에게 물어보세요.

1. 중복을 걱정해야 하나요?
2. 배열이 비어 있거나 요소가 하나만 있으면 어떻게 되나요? 예상되는 결과는 무엇인가요?
3. 배열의 인덱스 중 0 값을 고려/무시해야 합니까? 0을 포함하는 인덱스를 제외하고 다른 모든 값은 0을 갖기 때문입니다.
4. 이 문제의 코너/에지 사례는 무엇입니까?

면접관과 위의 질문에 대해 논의한 후 문제 해결을 위한 다양한 접근 방식을 고안해 보세요.

1. 순진한 접근 방식/무차별 대입.
2. 모든 요소의 산물.
3. 좌우 제품
4. 접두사 및 접미사 합계.

접근법 1: 순진함/무차별 대입

직관

무차별 접근 방식을 사용하려면 두 개의 for 루프를 실행해야 합니다. 외부 루프 인덱스가 내부 루프 인덱스 값과 일치하면 제품을 건너뛰어야 합니다. 그렇지 않으면 제품을 진행합니다.

연산

1. 변수 초기화:
   • N = nums.length(입력 배열의 길이).
   • result = new int[N] (결과를 저장할 배열).
2. 외부 루프(각 요소를 숫자 단위로 반복):
   • i = 0 ~ N-1의 경우: currentProduct 초기화 = 1.
3. 내부 루프(현재 요소의 곱 계산), j = 0 ~ N-1인 경우:
   • i == j인 경우 continue를 사용하여 현재 반복을 건너뜁니다.
   • currentProduct에 nums[j]를 곱합니다.
   • 현재제품을 결과[i]에 할당합니다.
4. 반품 결과.

암호

// 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;
}

복잡성 분석

1. 시간 복잡도: O(n^2), 외부 루프와 내부 루프에서 배열을 두 번 반복합니다.
2. 공간 복잡도: O(n), 우리가 사용한 보조 공간(결과[] 배열)에 대해

접근법 2: 배열의 곱 ❌

대부분의 개발자가 생각하는 방법 중 하나는 모든 요소의 곱 합계를 실행하고 곱 합계를 각 배열 값으로 나눈 다음 결과를 반환하는 것입니다.

의사코드

// 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‼️  

암호

// 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;
}

배열 요소 중 하나에 0이 포함되어 있으면 어떻게 되나요? ?

0을 포함하는 인덱스를 제외한 모든 인덱스의 값은 확실히 무한대입니다. 또한 코드에서 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)

접근 방식 3: 접두사 및 접미사 제품 찾기

제 웹사이트 https://ggorantala.dev의 배열 숙달 과정에서 접두사 및 접미사 합에 대해 자세히 알아보세요

직관과 공식

접두사와 접미사는 결과에 대한 알고리즘을 작성하기 전에 계산됩니다. 접두사 및 접미사 합계 공식은 다음과 같습니다.

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.

위 내용은 Leetcode : 자기를 제외한 배열의 곱의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!