我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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.
其他回答
下面是另一个简单的概念，可以解决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));
左旅行->右和保持保存产品。称之为过去。- > O (n) 旅行右->左保持产品。称之为未来。- > O (n) 结果[i] =过去[i-1] *将来[i+1] -> O(n) 过去[-1]= 1;和未来(n + 1) = 1;
O(n)
在这里添加我的javascript解决方案，因为我没有发现任何人建议这样做。 除法是什么，除了数从另一个数中得到一个数的次数吗?我计算了整个数组的乘积，然后遍历每个元素，并减去当前元素直到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;
}
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实现 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.
