[알고리즘] LeetCode - Product of Array Except Self

LeetCode - Product of Array Except Self

문제 설명

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example 1:

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

Constrains

It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Solution

  • null reference를 주의하자.

아래와 같이 생각해보면, 자신을 제외한 누적된 곱을 구할수있다.
/*
       값         1      2      3      4
앞에서부터 누적 곱    1     1X2   1X2X3 1X2X3X4
뒤에서부터 누적 곱 1X2X3X4 2X3X4   3X4     4
*/

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int numsLen=nums.length;
        int[] preProduct=new int[numsLen];
        int[] postProduct=new int[numsLen];
        int[] arrProduct=new int[numsLen];
        
        int productVal=1;
        for(int i=0; i<numsLen; i++){
            productVal=productVal*nums[i];
            preProduct[i]=productVal;
        }
        productVal=1;
         for(int i=numsLen-1; i>=0; i--){
            productVal=productVal*nums[i];
            postProduct[i]=productVal;
        }

        for(int j=0; j<numsLen; j++){
            if(j==0){
                arrProduct[j]= postProduct[j+1];
            }
            else if(j==numsLen-1){
                arrProduct[j]= preProduct[j-1];
            }
            else{
            arrProduct[j]= preProduct[j-1]*postProduct[j+1];
            }
            
        }

        return arrProduct;
    }
}

좋은 웹페이지 즐겨찾기