我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
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)
其他回答
这是我的代码:
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;
}
int[] arr1 = { 1, 2, 3, 4, 5 };
int[] product = new int[arr1.Length];
for (int i = 0; i < arr1.Length; i++)
{
for (int j = 0; j < product.Length; j++)
{
if (i != j)
{
product[j] = product[j] == 0 ? arr1[i] : product[j] * arr1[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));
根据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)
上下两次。在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;
}
