我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
下面是一个C实现 O(n)时间复杂度。 输入
#include<stdio.h>
int main()
{
int x;
printf("Enter The Size of Array : ");
scanf("%d",&x);
int array[x-1],i ;
printf("Enter The Value of Array : \n");
for( i = 0 ; i <= x-1 ; i++)
{
printf("Array[%d] = ",i);
scanf("%d",&array[i]);
}
int left[x-1] , right[x-1];
left[0] = 1 ;
right[x-1] = 1 ;
for( i = 1 ; i <= x-1 ; i++)
{
left[i] = left[i-1] * array[i-1];
}
printf("\nThis is Multiplication of array[i-1] and left[i-1]\n");
for( i = 0 ; i <= x-1 ; i++)
{
printf("Array[%d] = %d , Left[%d] = %d\n",i,array[i],i,left[i]);
}
for( i = x-2 ; i >= 0 ; i--)
{
right[i] = right[i+1] * array[i+1];
}
printf("\nThis is Multiplication of array[i+1] and right[i+1]\n");
for( i = 0 ; i <= x-1 ; i++)
{
printf("Array[%d] = %d , Right[%d] = %d\n",i,array[i],i,right[i]);
}
printf("\nThis is Multiplication of Right[i] * Left[i]\n");
for( i = 0 ; i <= x-1 ; i++)
{
printf("Right[%d] * left[%d] = %d * %d = %d\n",i,i,right[i],left[i],right[i]*left[i]);
}
return 0 ;
}
输出
Enter The Size of Array : 5
Enter The Value of Array :
Array[0] = 1
Array[1] = 2
Array[2] = 3
Array[3] = 4
Array[4] = 5
This is Multiplication of array[i-1] and left[i-1]
Array[0] = 1 , Left[0] = 1
Array[1] = 2 , Left[1] = 1
Array[2] = 3 , Left[2] = 2
Array[3] = 4 , Left[3] = 6
Array[4] = 5 , Left[4] = 24
This is Multiplication of array[i+1] and right[i+1]
Array[0] = 1 , Right[0] = 120
Array[1] = 2 , Right[1] = 60
Array[2] = 3 , Right[2] = 20
Array[3] = 4 , Right[3] = 5
Array[4] = 5 , Right[4] = 1
This is Multiplication of Right[i] * Left[i]
Right[0] * left[0] = 120 * 1 = 120
Right[1] * left[1] = 60 * 1 = 60
Right[2] * left[2] = 20 * 2 = 40
Right[3] * left[3] = 5 * 6 = 30
Right[4] * left[4] = 1 * 24 = 24
Process returned 0 (0x0) execution time : 6.548 s
Press any key to continue.
其他回答
根据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)
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));
技巧:
使用以下方法:
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，但这是解决它的方法。
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);
}
}
我想出了这个解决方案，我发现它很清楚，你觉得呢!?
我们可以先从列表中排除nums[j](其中j != i)，然后得到其余部分的乘积;下面是python解决这个难题的方法:
from functools import reduce
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]
