我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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));
下面是我用现代c++编写的解决方案。它使用std::transform，很容易记住。
在线代码(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 << " ";
}
还有一个解决方案，使用除法。有两次遍历。 把所有元素相乘，然后除以每个元素。
试试这个!
import java.util.*;
class arrProduct
{
public static void main(String args[])
{
//getting the size of the array
Scanner s = new Scanner(System.in);
int noe = s.nextInt();
int out[]=new int[noe];
int arr[] = new int[noe];
// getting the input array
for(int k=0;k<noe;k++)
{
arr[k]=s.nextInt();
}
int val1 = 1,val2=1;
for(int i=0;i<noe;i++)
{
int res=1;
for(int j=1;j<noe;j++)
{
if((i+j)>(noe-1))
{
int diff = (i+j)-(noe);
if(arr[diff]!=0)
{
res = res * arr[diff];
}
}
else
{
if(arr[i+j]!=0)
{
res= res*arr[i+j];
}
}
out[i]=res;
}
}
//printing result
System.out.print("Array of Product: [");
for(int l=0;l<out.length;l++)
{
if(l!=out.length-1)
{
System.out.print(out[l]+",");
}
else
{
System.out.print(out[l]);
}
}
System.out.print("]");
}
}
