번호 배열이 주어지면 다른 모든 번호의 제품 배열을 반환합니다(분할 없음).

번호 배열이 주어지면 다른 모든 번호의 제품 배열을 반환합니다(분할 없음).

취업 면접에서 이런 질문을 받았는데, 다른 사람들이 어떻게 해결할지 궁금합니다.저는 자바가 가장 편하지만, 다른 언어로 된 솔루션은 환영합니다.

배열이 때, 숫들의배고때할려을열자,때,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)나눗셈을 사용하지 않고

다유전자 윤활제 방법은 다음과 같습니다.

이 방법은 어레이를 구성하는 것입니다(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];
int 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) 솔루션이 필요한 경우 다음을 수행할 수 있습니다(제 생각에는 명확하지 않습니다).

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

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

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

다음은 수정을 수행하기 위한 작은 재귀 함수(C++)입니다. O의 공간(이 필요합니다 (으)로 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;
}

이것은 자바로 해결하려는 저의 시도입니다.표준 포맷이 아닌 것은 죄송하지만 코드가 중복되는 부분이 많고, 읽을 수 있도록 하기 위해서는 이것이 최선입니다.

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]"
    }
}

은 프루불변량은다같습다니과음다같▁the니입니다.pi = nums[0] * nums[1] *.. nums[i-1]그리고.pj = nums[N-1] * nums[N-2] *.. nums[j+1].i왼쪽에 있는 부분은 "논리적인" 논리이고, 그리고.j오른쪽 부분은 "역설" 논리입니다.

---

재귀 원라이너

재스밋은 재귀적인 해결책을 제시했습니다; 저는 그것을 이것으로 만들었습니다.자바 원라이너.내부 수정을 수행합니다.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]);
    }

1. 왼쪽으로 이동->오른쪽으로 이동하여 제품을 계속 저장합니다.지나간 일이라고 해요. -> O(n)
2. 우측통행 -> 좌측통행 상품 보관Call it Future. -> O(n)
3. 결과[i] = 과거[i-1] * 미래[i+1] -> O(n)
4. 과거 [-1] = 1, 미래 [n+1] = 1;

O(n)

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));

여기 현대 C++에 대한 저의 해결책이 있습니다.은 사다니합용을 합니다.std::transform그리고 기억하기가 꽤 쉽습니다.

온라인 코드(완드박스).

#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

vector<int>& multiply_up(vector<int>& v){
    v.insert(v.begin(),1);
    transform(v.begin()+1, v.end()
             ,v.begin()
             ,v.begin()+1
             ,[](auto const& a, auto const& b) { return b*a; }
             );
    v.pop_back();
    return v;
}

int main() {
    vector<int> v = {1,2,3,4,5};
    auto vr = v;

    reverse(vr.begin(),vr.end());
    multiply_up(v);
    multiply_up(vr);
    reverse(vr.begin(),vr.end());

    transform(v.begin(),v.end()
             ,vr.begin()
             ,v.begin()
             ,[](auto const& a, auto const& b) { return b*a; }
             );

    for(auto& i: v) cout << i << " "; 
}

각 요소의 왼쪽과 오른쪽에 있는 숫자의 곱을 미리 계산합니다.모든 요소에 대해 원하는 값은 인접 요소의 제품입니다.

#include <stdio.h>

unsigned array[5] = { 1,2,3,4,5};

int main(void)
{
unsigned idx;

unsigned left[5]
        , right[5];
left[0] = 1;
right[4] = 1;

        /* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
        left[idx] = left[idx-1] * array[idx-1];
        }

        /* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
        right[idx] = right[idx+1] * array[idx+1];
        }

for (idx=0; idx <5 ; idx++) {
        printf("[%u] Product(%u*%u) = %u\n"
                , idx, left[idx] , right[idx]  , left[idx] * right[idx]  );
        }

return 0;
}

결과:

$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24

(업데이트: 이제 자세히 살펴보니 위의 Michael Anderson, Daniel Migowski 및 다유전자 윤활제와 동일한 방법을 사용합니다.)

까다로운:

다음을 사용합니다.

public int[] calc(int[] params) {

int[] left = new int[n-1]
in[] right = new int[n-1]

int fac1 = 1;
int fac2 = 1;
for( int i=0; i<n; i++ ) {
    fac1 = fac1 * params[i];
    fac2 = fac2 * params[n-i];
    left[i] = fac1;
    right[i] = fac2; 
}
fac = 1;

int[] results = new int[n];
for( int i=0; i<n; i++ ) {
    results[i] = left[i] * right[i];
}

네, 저는 제가 i 대신 i-1을 놓쳤다고 확신하지만, 그것이 그것을 해결하는 방법입니다.

이것은 O(n^2)이지만 f#는 너무 아름답습니다.

List.fold (fun seed i -> List.mapi (fun j x -> if i=j+1 then x else x*i) seed) 
          [1;1;1;1;1]
          [1..5]

O(N^(3/2) 비최적 솔루션도 있습니다.하지만, 그것은 꽤 흥미롭습니다.

먼저 크기 N^0.5의 각 부분 곱셈을 사전 처리합니다(이것은 O(N) 시간 복잡도에서 수행됨).그런 다음 각 숫자의 다른 값의 배수에 대한 계산은 2*O(N^0.5) 시간 내에 수행될 수 있습니다(왜냐하면 다른 숫자의 마지막 요소(N^0.5) - 1)만 곱하면 되고 결과는 현재 숫자의 그룹에 속하는 (N^0.5) - 1) 숫자로 곱하면 되기 때문입니다.각 숫자에 대해 이렇게 하면 O(N^(3/2)) 시간을 얻을 수 있습니다.

예:

4 6 7 2 3 1 9 5 8

부분 결과: 4*6*7 = 1682*3*1 = 69*5*8 = 360

3의 값을 계산하려면 다른 그룹의 값 168*360을 곱한 다음 2*1을 곱해야 합니다.

public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5 };
    int[] result = { 1, 1, 1, 1, 1 };
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < i; j++) {
            result[i] *= arr[j];

        }
        for (int k = arr.length - 1; k > i; k--) {
            result[i] *= arr[k];
        }
    }
    for (int i : result) {
        System.out.println(i);
    }
}

제가 생각해 낸 이 해결책은 매우 명확하다는 것을 알았습니다. 어떻게 생각하세요!?

Billz 답변을 기준으로--죄송하지만, 목록에서 중복된 항목을 올바르게 처리하는 스칼라 버전이 있으며, 아마도 O(n)일 것입니다.

val list1 = List(1, 7, 3, 3, 4, 4)
val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)}
view.force

반환:

List(1008, 144, 336, 336, 252, 252)

이것을 제안하는 사람을 찾지 못했기 때문에 자바스크립트 솔루션을 여기에 추가합니다.다른 숫자에서 숫자를 추출할 수 있는 횟수를 세는 것 외에 나눌 수 있는 것은 무엇입니까?저는 전체 배열의 곱을 계산한 다음 각 요소에 대해 반복하고 현재 요소를 0으로 뺄셈하는 과정을 거쳤습니다.

//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
  var res = [];
  var totalProduct = 1;
  //calculate the total product
  for(var i = 0; i < input.length; i++){
    totalProduct = totalProduct * input[i];
  }
  //populate the result array by "dividing" each value
  for(var i = 0; i < input.length; i++){
    var timesSubstracted = 0;
    var divisor = input[i];
    var dividend = totalProduct;
    while(divisor <= dividend){
      dividend = dividend - divisor;
      timesSubstracted++;
    }
    res.push(timesSubstracted);
  }
  return res;
}

딱 2개만 위아래로.O(N)에서 수행한 작업

private static int[] multiply(int[] numbers) {
        int[] multiplied = new int[numbers.length];
        int total = 1;

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

        for (int j = numbers.length - 2; j >= 0; j--) {
            total *= numbers[j + 1];
            multiplied[j] = total * multiplied[j];
        }

        return multiplied;
    }

def productify(arr, prod, i):
    if i < len(arr):
        prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1)
        retval = productify(arr, prod, i + 1)
        prod[i] *= retval
        return retval * arr[i]
    return 1

if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5]
    prod = []
    productify(arr, prod, 0)
    print(prod)

이 솔루션은 C/C++ 솔루션이라고 할 수 있습니다.a[n]와 같은 n개의 요소를 포함하는 배열 "a"가 있다고 가정하면 유사 코드는 다음과 같습니다.

for(j=0;j<n;j++)
  { 
    prod[j]=1;

    for (i=0;i<n;i++)
    {   
        if(i==j)
        continue;  
        else
        prod[j]=prod[j]*a[i];
  }

하나 더 해결책, 분열을 이용하는 것.두 번 횡보하는.모든 요소를 곱한 다음 각 요소로 나누기 시작합니다.

{-sqrt(n) 하위 집합을 사용하는 재귀 솔루션입니다.O(n) 단위로 실행됩니다.

sqrt(n) 크기의 sqrt(n) 부분 집합에 대한 해를 재귀적으로 계산합니다. 
그런 다음 각 부분 집합의 곱 합계에 대해 반복합니다.
그런 다음 각 부분 집합의 각 요소에 대해 다음을 사용하여 곱을 계산합니다.다른 모든 제품의 제품 합계
그런 다음 모든 부분 집합을 평평하게 만듭니다.

실행 시간의 반복은 T(n) = sqrt(n)*T(sqrt(n) + T(sqrt(n)) + n입니다.
T(n) ≤ cn in O(n)라고 가정합니다.

T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + nsqrt(n)*c*sqrt(n) + c*sqrt(n) + nc*n + c*sqrt(n) + n(2c+1)*nO(n)
천장(sqrt(n))은 이진 검색을 사용하여 계산할 수 있습니다.및 O(logn) 반복(sqrt 명령이 허용되지 않는 경우)
-}
기타 제품 [] = []기타 제품 [x] = [1]기타 제품 [x,y] = [y,x]기타 제품 a = foldl' (++) [] $ zipWith (\sp -> 지도 (*p)s) 해결된 하위 집합기타 제품어디에n = 길이 a
부분 집합 크기.1 < s < n이 필요합니다.s = 천장 $ sqrt $ 위치적분 n
solvedSubsets = 다른 제품 서브셋 매핑하위 집합 기타 제품 = 기타 제품 $ 지도 제품 하위 집합
부분 집합 = 역 $ 루프 a []여기서 루프 [] ac = acloop acc = loop (drop a) ((take a):acc)

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

int multiply(int a[],int n,int nextproduct,int i)
{
    int prevproduct=1;
    if(i>=n)
        return prevproduct;
    prevproduct=multiply(a,n,nextproduct*a[i],i+1);
    printf(" i=%d > %d\n",i,prevproduct*nextproduct);
    return prevproduct*a[i];
}

int main()
{
    int a[]={2,4,1,3,5};
    multiply(a,5,1,0);
    return 0;
}

다음은 C#을 사용한 약간의 기능적인 예입니다.

            Func<long>[] backwards = new Func<long>[input.Length];
            Func<long>[] forwards = new Func<long>[input.Length];

            for (int i = 0; i < input.Length; ++i)
            {
                var localIndex = i;
                backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex];
                forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex];
            }

            var output = new long[input.Length];
            for (int i = 0; i < input.Length; ++i)
            {
                if (0 == i)
                {
                    output[i] = forwards[i + 1]();
                }
                else if (input.Length - 1 == i)
                {
                    output[i] = backwards[i - 1]();
                }
                else
                {
                    output[i] = forwards[i + 1]() * backwards[i - 1]();
                }
            }

생성된 Funcs의 반재귀 때문에 이것이 O(n)인지 완전히 확신할 수는 없지만, 제 테스트는 시간에 O(n)임을 나타내는 것 같습니다.

다음은 스칼라의 코드입니다.

val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))

그러면 다음이 인쇄됩니다.

120
60
40
30
24

프로그램은 현재 요소(_!= 요소)를 필터링하고 reduclearLeft 메서드를 사용하여 새 목록을 곱합니다.게으른 평가를 위해 스칼라뷰나 Iterator를 사용하면 O(n)가 될 것 같습니다.

이것은 Java // 재귀 솔루션입니다. 주 제품(a,1,0)에서 다음과 같이 호출됩니다.

public static double product(double[] a, double fwdprod, int index){
    double revprod = 1;
    if (index < a.length){
        revprod = product2(a, fwdprod*a[index], index+1);
        double cur = a[index];
        a[index] = fwdprod * revprod;
        revprod *= cur;
    }
    return revprod;
}

O(n) 런타임을 사용하는 깔끔한 솔루션:

1. 각 요소에 대해 그 이전에 발생한 모든 요소의 곱을 계산하고 배열 "pre"에 저장합니다.
2. 각 요소에 대해 해당 요소 이후에 발생하는 모든 요소의 곱을 계산하고 배열 "포스트"에 저장합니다.

3. 요소 i에 대한 최종 배열 "결과"를 만듭니다.

   result[i] = pre[i-1]*post[i+1];
   

여기 ptyhon 버전이 있습니다.

  # This solution use O(n) time and O(n) space
  def productExceptSelf(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    N = len(nums)
    if N == 0: return

    # Initialzie list of 1, size N
    l_prods, r_prods = [1]*N, [1]*N

    for i in range(1, N):
      l_prods[i] = l_prods[i-1] * nums[i-1]

    for i in reversed(range(N-1)):
      r_prods[i] = r_prods[i+1] * nums[i+1]

    result = [x*y for x,y in zip(l_prods,r_prods)]
    return result

  # This solution use O(n) time and O(1) space
  def productExceptSelfSpaceOptimized(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    N = len(nums)
    if N == 0: return

    # Initialzie list of 1, size N
    result = [1]*N

    for i in range(1, N):
      result[i] = result[i-1] * nums[i-1]

    r_prod = 1
    for i in reversed(range(N)):
      result[i] *= r_prod
      r_prod *= nums[i]

    return result

나는 C#에 익숙합니다.

    public int[] ProductExceptSelf(int[] nums)
    {
        int[] returnArray = new int[nums.Length];
        List<int> auxList = new List<int>();
        int multTotal = 0;

        // If no zeros are contained in the array you only have to calculate it once
        if(!nums.Contains(0))
        {
            multTotal = nums.ToList().Aggregate((a, b) => a * b);

            for (int i = 0; i < nums.Length; i++)
            {
                returnArray[i] = multTotal / nums[i];
            }
        }
        else
        {
            for (int i = 0; i < nums.Length; i++)
            {
                auxList = nums.ToList();
                auxList.RemoveAt(i);
                if (!auxList.Contains(0))
                {
                    returnArray[i] = auxList.Aggregate((a, b) => a * b);
                }
                else
                {
                    returnArray[i] = 0;
                }
            }
        }            

        return returnArray;
    }

선형 O(n) 시간의 간단한 스칼라 버전은 다음과 같습니다.

defitProductEff(단위:Seq[Int]:Seq[Int] = {
//이 요소의 왼쪽에 모든 요소의 곱이 있는 목록을 만듭니다.왼쪽 = in.foldLeft((1, Seq.empty[Int]))(ac, i) => (i * ac._1, ac._2:+ ac._1)에서 val._2
//이 요소의 오른쪽에 모든 요소의 곱이 있는 목록을 만듭니다. 이 값은 이전 단계와 동일하지만 반대입니다.오른쪽에서 val = in.reverse.foldLeft((1,Seq.empty[Int]))(ac,i) => (i * ac._1,ac._2:+ ac._1)._2.304
//인덱스에서 두 목록을 제품별로 표시in.vmap.map(i => 왼쪽(i) * 오른쪽(i)에서)

}

이것은 근본적으로 답이 왼쪽과 오른쪽에 모든 요소의 곱을 갖는 배열이기 때문에 작동합니다.

import java.util.Arrays;

public class Pratik
{
    public static void main(String[] args)
    {
        int[] array = {2, 3, 4, 5, 6};      //  OUTPUT: 360  240  180  144  120
        int[] products = new int[array.length];
        arrayProduct(array, products);
        System.out.println(Arrays.toString(products));
    }

    public static void arrayProduct(int array[], int products[])
    {
        double sum = 0, EPSILON = 1e-9;

        for(int i = 0; i < array.length; i++)
            sum += Math.log(array[i]);

        for(int i = 0; i < array.length; i++)
            products[i] = (int) (EPSILON + Math.exp(sum - Math.log(array[i])));
    }
}

출력:

[360, 240, 180, 144, 120]

시간 복잡도 : O(n)

공간 복잡도: O(1)

언급URL : https://stackoverflow.com/questions/2680548/given-an-array-of-numbers-return-array-of-products-of-all-other-numbers-no-div