给定一组数字，返回所有其他数字的产品数组（无分区）-Java 学习之路

165

我在求职面试中被问到这个问题，我想知道其他人如何解决这个问题 . 我对Java最熟悉，但欢迎使用其他语言的解决方案 .

给定一组数字，nums，返回一组数字产品，其中products [i]是所有nums [j]，j！= i的乘积 . 输入：[1,2,3,4,5]
输出：[（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）中执行此操作而不使用除法 .

30 回答

这是解决 O(N) 中问题的另一个简单概念 .

int[] arr = new int[] {1, 2, 3, 4, 5};
        int[] outArray = new int[arr.length]; 
        for(int i=0;i<arr.length;i++){
            int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
            outArray[i] = res/arr[i];
        }
        System.out.println(Arrays.toString(outArray));

回复于 2024-04-18T14:21:43+08:00

function solution($array)
{
    $result = [];
    foreach($array as $key => $value){
        $copyOfOriginalArray = $array;
        unset($copyOfOriginalArray[$key]);
        $result[$key] = multiplyAllElemets($copyOfOriginalArray);
    }
    return $result;
}

/**
 * multiplies all elements of array
 * @param $array
 * @return int
 */
function multiplyAllElemets($array){
    $result = 1;
    foreach($array as $element){
        $result *= $element;
    }
    return $result;
}

$array = [1, 9, 2, 7];

print_r(solution($array));

回复于 2024-04-18T14:21:43+08:00

223

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）你也可以这样做（这不太清楚恕我直言）

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

回复于 2024-04-18T14:21:43+08:00

这是一个小的递归函数（在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;
}

回复于 2024-04-18T14:21:43+08:00

预先计算每个元素左侧和右侧的数字乘积 . 对于每个元素，期望的 Value 是它的neigbors产品的产物 .

#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和上面的polygenelubricants相同的方法）

回复于 2024-04-18T14:21:43+08:00

这是我尝试用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 部分是"prefix"逻辑，右侧的 j 部分是"suffix"逻辑 .

递归单行

Jasmeet给了一个（漂亮！）递归解决方案;我把它变成了这个（丑陋的）Java单线程 . 它使用堆栈中的 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]"

回复于 2024-04-18T14:21:43+08:00

将Michael Anderson的解决方案翻译成Haskell：

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

回复于 2024-04-18T14:21:43+08:00

悄悄地规避“不分裂”规则：

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

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

回复于 2024-04-18T14:21:43+08:00

在这里，简单而干净的解决方案具有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]);
    }

回复于 2024-04-18T14:21:43+08:00

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

回复于 2024-04-18T14:21:43+08:00

0
- 左行 - >正确并继续保存产品 . 称之为过去 . - > O（n）
- 旅行权 - >左保留产品 . 称之为未来 . - > O（n）
- 结果[i] =过去[i-1] * future [i 1] - > O（n）
- 过去[-1] = 1;和未来[n 1] = 1;
上）
回复于 2024-04-18T14:21:43+08:00

这是我在现代C中的解决方案 . 它使用 std::transform 并且很容易记住 .

Online code (wandbox).

#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 << " "; 
}

回复于 2024-04-18T14:21:43+08:00

这是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]

回复于 2024-04-18T14:21:43+08:00

整蛊：

使用以下内容：

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-1而不是我，但这就是解决问题的方法 .

回复于 2024-04-18T14:21:43+08:00

9

还有一个O（N ^（3/2）） non-optimal 解决方案 . 不过，这很有意思 .

首先预处理大小为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 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360

要计算3的值，需要将其他组的值乘以168 * 360，然后再乘以2 * 1 .

回复于 2024-04-18T14:21:43+08:00

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

我想出了这个解决方案，我发现它很清楚你怎么想！？

回复于 2024-04-18T14:21:43+08:00

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

arr = [1,2,3,4,5] prod = [] productify（arr，prod，0）print prod

回复于 2024-04-18T14:21:43+08:00

在这里添加我的JavaScript解决方案，因为我没有找到任何人建议这个 . 什么是除法，除了计算从另一个数字中提取数字的次数？我经历了计算整个数组的乘积，然后迭代每个元素，并将当前元素减去零：

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

回复于 2024-04-18T14:21:43+08:00

我习惯用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;
    }

回复于 2024-04-18T14:21:43+08:00

1
那么，这个解决方案可以被认为是C / C的解决方案 . 假设我们有一个包含n个元素的数组“a”，如[n]，那么伪代码如下所示 .
```
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];
  }
```
回复于 2024-04-18T14:21:43+08:00
2

还有一个解决方案，使用除法 . 两次遍历 . 将所有元素相乘，然后开始按每个元素分割 .

回复于 2024-04-18T14:21:43+08:00

{-
Recursive solution using sqrt(n) subsets. Runs in O(n).

Recursively computes the solution on sqrt(n) subsets of size sqrt(n). 
Then recurses on the product sum of each subset.
Then for each element in each subset, it computes the product with
the product sum of all other products.
Then flattens all subsets.

Recurrence on the run time is T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n

Suppose that T(n) ≤ cn in O(n).

T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n
    ≤ sqrt(n)*c*sqrt(n) + c*sqrt(n) + n
    ≤ c*n + c*sqrt(n) + n
    ≤ (2c+1)*n
    ∈ O(n)

Note that ceiling(sqrt(n)) can be computed using a binary search 
and O(logn) iterations, if the sqrt instruction is not permitted.
-}

otherProducts [] = []
otherProducts [x] = [1]
otherProducts [x,y] = [y,x]
otherProducts a = foldl' (++) [] $ zipWith (\s p -> map (*p) s) solvedSubsets subsetOtherProducts
    where 
      n = length a

      -- Subset size. Require that 1 < s < n.
      s = ceiling $ sqrt $ fromIntegral n

      solvedSubsets = map otherProducts subsets
      subsetOtherProducts = otherProducts $ map product subsets

      subsets = reverse $ loop a []
          where loop [] acc = acc
                loop a acc = loop (drop s a) ((take s a):acc)

回复于 2024-04-18T14:21:43+08:00

这是我的代码：

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

回复于 2024-04-18T14:21:43+08:00

这是一个使用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]();
                }
            }

我不完全确定这是O（n），由于创建的Funcs的半递归，但我的测试似乎表明它是O（n）及时 .

回复于 2024-04-18T14:21:43+08:00

5
这里完整的是Scala中的代码：
```
val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))
```
这将打印出以下内容：
```
120
60
40
30
24
```
该程序将过滤掉当前的元素（_！=ELEM）;并使用reduceLeft方法将新列表相乘 . 如果你使用scala视图或Iterator进行惰性评估，我认为这将是O（n） .
回复于 2024-04-18T14:21:43+08:00

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

回复于 2024-04-18T14:21:43+08:00

0
O（n）运行时的简洁解决方案：
- 对于每个元素，计算在此之前出现的所有元素的乘积，并将其存储在数组"pre"中 .
- 对于每个元素计算在该元素之后出现的所有元素的乘积并将其存储在数组中"post"
- 为元素i创建最终数组“result”，
```
result[i] = pre[i-1]*post[i+1];
```
回复于 2024-04-18T14:21:43+08:00

我们可以先从列表中排除 nums[j] （其中 j != i ），然后得到其余的产品;以下是解决这个难题的 python way ：

def products(nums):
    return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print products([1, 2, 3, 4, 5])

[out]
[120, 60, 40, 30, 24]

回复于 2024-04-18T14:21:43+08:00

1
根据Billz回答 - 抱歉我无法发表评论，但这里有一个正确处理列表中重复项的scala版本，可能是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)
```
回复于 2024-04-18T14:21:43+08:00

我有一个解决方案，下面提供 O(n) 空间和 O(n^2) 时间复杂度，

public static int[] findEachElementAsProduct1(final int[] arr) {

        int len = arr.length;

//        int[] product = new int[len];
//        Arrays.fill(product, 1);

        int[] product = IntStream.generate(() -> 1).limit(len).toArray();


        for (int i = 0; i < len; i++) {

            for (int j = 0; j < len; j++) {

                if (i == j) {
                    continue;
                }

                product[i] *= arr[j];
            }
        }

        return product;
    }

回复于 2024-04-18T14:21:43+08:00

给定一组数字，返回所有其他数字的产品数组（无分区）

30 回答

递归单行

相关问题