我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用Java，但也欢迎使用其他语言的解决方案。
给定一个数字数组nums，返回一个数字数组products，其中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)中不使用除法来做这个。
当前回答
最近有人问我这个问题，虽然我不能得到O(N)，但我有一个不同的方法(不幸的是O(N²))，但我想无论如何都要分享。
首先转换为列表<Integer>。
遍历原始数组array.length()次。
使用while循环乘下一组所需的数字:
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
然后将res添加到一个新数组(当然，您已经在前面声明了)，然后将数组[i]的值添加到List，依此类推。
我知道这不会有太大的用处，但这是我在面试的压力下想到的:)
int[] array = new int[]{1, 2, 3, 4, 5};
List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
int[] newarray = new int[array.length];
int res = 1;
for (int i = 0; i < array.length; i++) {
int temp = i;
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
newarray[i] = res;
list.add(array[i]);
res = 1;
}
输出:[24,120,60,40,30]
其他回答
给你，简单干净的解决方案，复杂度为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]);
}
int[] b = new int[] { 1, 2, 3, 4, 5 };
int j;
for(int i=0;i<b.Length;i++)
{
int prod = 1;
int s = b[i];
for(j=i;j<b.Length-1;j++)
{
prod = prod * b[j + 1];
}
int pos = i;
while(pos!=-1)
{
pos--;
if(pos!=-1)
prod = prod * b[pos];
}
Console.WriteLine("\n Output is {0}",prod);
}
php版本 使用不除法的array_product函数。 如果我们将i的值临时设为1，那么数组product将完全满足我们的需要
<?php
function product($key, $arr)
{
$arr[$key] = 1;
return array_product($arr);
};
$arr = [1, 2, 3, 4, 5];
$newarr = array();
foreach ($arr as $key => $value) {
$newarr[$key] = product($key, $arr);
}
print_r($newarr);
这是O(n²)但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]
技巧:
使用以下方法:
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而不是I，但这是解决它的方法。
