[arrays] 숫자 배열이 주어지면 다른 모든 숫자의 제품 배열을 반환하십시오 (나눗셈 없음)

Program / 글쓴이

면접에서이 질문을 받았고 다른 사람들이 어떻게 해결할 수 있는지 알고 싶습니다. Java에 가장 익숙하지만 다른 언어로 된 솔루션도 환영합니다.

숫자의 배열을 지정해, nums숫자의 배열 반환 products, products[i]모두의 제품입니다 nums[j], j != i.

Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
      = [120, 60, 40, 30, 24]

O(N)나누기를 사용하지 않고이 작업을 수행해야합니다 .

답변

polygenelubricants 방법에 대한 설명 은 다음과 같습니다. 트릭은 배열을 구성하는 것입니다 (4 가지 요소의 경우).

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

둘 다 왼쪽과 오른쪽 가장자리에서 각각 시작하여 O (n)에서 수행 할 수 있습니다.

그런 다음 두 배열 요소에 요소를 곱하면 필요한 결과가 나타납니다.

내 코드는 다음과 같습니다.

int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i) {
  products_below[i]=p;
  p*=a[i];
}

int products_above[N];
p=1;
for(int i=N-1;i>=0;--i) {
  products_above[i]=p;
  p*=a[i];
}

int products[N]; // This is the result
for(int i=0;i<N;++i) {
  products[i]=products_below[i]*products_above[i];
}

우주에서 O (1)이되어야한다면 이렇게 할 수 있습니다 (IMHO가 덜 명확합니다)

int a[N] // This is the input
int products[N];

// Get the products below the current index
p=1;
for(int i=0;i<N;++i) {
  products[i]=p;
  p*=a[i];
}

// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i) {
  products[i]*=p;
  p*=a[i];
}

답변

다음은 modofication을 수행하는 작은 재귀 함수 (C ++)입니다. 그래도 O (n) 여분의 공간 (스택)이 필요합니다. 배열이 a에 있고 N이 배열 길이를 보유한다고 가정하면

int multiply(int *a, int fwdProduct, int indx) {
    int revProduct = 1;
    if (indx < N) {
       revProduct = multiply(a, fwdProduct*a[indx], indx+1);
       int cur = a[indx];
       a[indx] = fwdProduct * revProduct;
       revProduct *= cur;
    }
    return revProduct;
}

답변

Java로 해결하려는 나의 시도는 다음과 같습니다. 비표준 형식에 대한 사과지만 코드에는 많은 중복이 있으며 이것이 읽기 가능하도록 최선의 방법입니다.

import java.util.Arrays;

public class Products {
    static int[] products(int... nums) {
        final int N = nums.length;
        int[] prods = new int[N];
        Arrays.fill(prods, 1);
        for (int
           i = 0, pi = 1    ,  j = N-1, pj = 1  ;
           (i < N)         && (j >= 0)          ;
           pi *= nums[i++]  ,  pj *= nums[j--]  )
        {
           prods[i] *= pi   ;  prods[j] *= pj   ;
        }
        return prods;
    }
    public static void main(String[] args) {
        System.out.println(
            Arrays.toString(products(1, 2, 3, 4, 5))
        ); // prints "[120, 60, 40, 30, 24]"
    }
}

루프 불변량은 pi = nums[0] * nums[1] *.. nums[i-1]및 pj = nums[N-1] * nums[N-2] *.. nums[j+1]입니다. i왼쪽 부분은 “접두사”논리이고, j오른쪽 부분은 “접미사”논리이다.

재귀 원 라이너

Jasmeet 은 (아름다운!) 재귀 솔루션을 제공했습니다. 나는 이것을 (끔찍한!) Java one-liner로 바꾸었다. 그것은 수행 의 장소 수정 과, O(N)스택의 임시 공간.

static int multiply(int[] nums, int p, int n) {
    return (n == nums.length) ? 1
      : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))
          + 0*(nums[n] *= p);
}

int[] arr = {1,2,3,4,5};
multiply(arr, 1, 0);
System.out.println(Arrays.toString(arr));
// prints "[120, 60, 40, 30, 24]"

답변

Michael Anderson의 솔루션을 Haskell로 번역 : 

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

답변

“분열 없음”규칙을 우회적으로 우회 :

sum = 0.0
for i in range(a):
  sum += log(a[i])

for i in range(a):
  output[i] = exp(sum - log(a[i]))

답변

O (N) 복잡성을 가진 간단하고 깨끗한 솔루션입니다.

int[] a = {1,2,3,4,5};
    int[] r = new int[a.length];
    int x = 1;
    r[0] = 1;
    for (int i=1;i<a.length;i++){
        r[i]=r[i-1]*a[i-1];
    }
    for (int i=a.length-1;i>0;i--){
        x=x*a[i];
        r[i-1]=x*r[i-1];
    }
    for (int i=0;i<r.length;i++){
        System.out.println(r[i]);
    }

답변

C ++, O (n) :

long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies<int>());
transform(in.begin(), in.end(), back_inserter(res),
          bind1st(divides<long long>(), prod));