Typescript Coding Chronicles: 자기를 제외한 배열의 산물

문제 설명:

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

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

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

예시 1:

• 입력: 숫자 = [1,2,3,4]
• 출력: [24,12,8,6]

예시 2:

• 입력: 숫자 = [-1,1,0,-3,3]
• 출력: [0,0,9,0,0]

제약:

• 2 <= nums.length <= 10^5
• -30 <= 숫자[i] <= 30
• nums의 접두사 또는 접미사의 곱은 32비트 정수에 맞도록 보장됩니다.

후속 조치:

O(1) 추가 공간 복잡도 문제를 해결할 수 있나요? (출력 배열은 공간 복잡도 분석을 위한 추가 공간으로 계산되지 않습니다.)

초기 사고 과정:

이 문제를 해결하려면 나누기 연산을 사용하지 않고 현재 요소를 제외한 모든 요소의 곱을 계산해야 합니다. 이는 어레이에 대해 두 번의 패스를 사용하여 수행할 수 있습니다.

1. 각 요소의 접두어 곱을 계산합니다.
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은 배열의 길이입니다. 배열을 세 번 반복합니다.
• 공간 복잡도: 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;
}




<h3>
  
  
  시간 복잡도 분석:
</h3>

<ul>
<li>
<strong>시간 복잡도:</strong> O(n), 여기서 n은 배열의 길이입니다. 배열을 두 번 반복합니다.</li>
<li>
<strong>공간 복잡도:</strong> O(1), 출력 배열을 사용하여 중간 결과를 저장하고 추가 공간을 사용하지 않기 때문입니다.</li>
</ul>

<h3>
  
  
  기본 솔루션에 비해 개선된 사항:
</h3>

<ul>
<li>최적화된 솔루션은 중간 결과에 대한 출력 배열을 사용하여 공간 복잡도를 O(1)로 줄입니다.</li>
</ul>

<h2>
  
  
  엣지 케이스 및 테스트:
</h2>

<h3>
  
  
  엣지 케이스:
</h3>

<ol>
<li>배열에 0이 포함되어 있습니다.</li>
<li>배열에 음수가 포함되어 있습니다.</li>
<li>배열 길이는 최소(2) 또는 최대(10^5) 제한입니다.</li>
</ol>

<h3>
  
  
  테스트 사례:
</h3>



<pre class="brush:php;toolbar:false">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]

일반적인 문제 해결 전략:

1. 문제 이해: 문제 설명을 주의 깊게 읽고 요구 사항과 제약 조건을 이해하세요.
2. 주요 작업 식별: 접두사 및 접미사 제품 계산과 같이 필요한 주요 작업을 결정합니다.
3. 가독성 최적화: 명확하고 간결한 논리를 사용하여 코드를 쉽게 따라갈 수 있도록 합니다.
4. 철저한 테스트: 엣지 케이스를 포함한 다양한 케이스로 솔루션을 테스트하여 정확성을 확인하세요.

유사한 문제 식별:

1. 접두사 합계 배열:

   • 범위 쿼리에 대한 접두사 합계를 계산해야 하는 문제.
   • 예: 범위 합계 쿼리

2. 내부 알고리즘:

   • 제한된 추가 공간에서 작업을 수행해야 하는 문제
   • 예: 배열을 오른쪽으로 k만큼 회전합니다.

3. 배열 조작:

   • 특정 조건에 따라 배열을 수정해야 하는 문제
   • 예: 0을 배열의 끝으로 이동합니다.

결론:

• self를 제외한 배열의 곱을 계산하는 문제는 추가 공간이 있는 기본 접근 방식과 최적화된 내부 접근 방식을 모두 사용하여 효율적으로 해결할 수 있습니다.
• 문제를 이해하고 관리 가능한 부분으로 나누는 것이 중요합니다.
• 명확한 논리를 사용하고 가독성을 최적화하면 솔루션을 쉽게 따라갈 수 있습니다.
• 다양한 엣지 케이스로 테스트하여 견고성을 보장합니다.
• 문제의 패턴을 인식하면 다른 문제에 유사한 솔루션을 적용하는 데 도움이 될 수 있습니다.

이러한 문제와 전략을 연습함으로써 문제 해결 능력을 향상시키고 다양한 코딩 과제에 더 잘 대비할 수 있습니다.

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