我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
技巧:
使用以下方法:
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，但这是解决它的方法。
其他回答
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));
我用Javascript想出了两个解决方案，一个有除法，一个没有
//不除法 函数methodOne(arr) { 加勒比海盗。Map (item => { 加勒比海盗。Reduce ((result, num) => { If (num !== item) { 结果=结果* num; ｝ 返回结果; }, 1) })； ｝ //使用除法 函数methodTwo(arr) { Var mul = arr。Reduce ((result, num) => { 结果=结果* num; 返回结果; }, 1) 加勒比海盗。Map (item => mul/item); ｝ console.log(methodOne([1,2,3,4,5])); console.log(methodTwo([1,2,3,4,5]));
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];
}
}
}
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);
}
}
我想出了这个解决方案，我发现它很清楚，你觉得呢!?
多基因润滑剂方法的一个解释是:
诀窍是构造数组(在4个元素的情况下):
{ 1, a[0], a[0]*a[1], a[0]*a[1]*a[2], }
{ a[1]*a[2]*a[3], a[2]*a[3], a[3], 1, }
这两种方法都可以在O(n)中分别从左右边开始。
然后，将两个数组逐个元素相乘，得到所需的结果。
我的代码看起来是这样的:
int a[N] // This is the input
int products_below[N];
int p = 1;
for (int i = 0; i < N; ++i) {
products_below[i] = p;
p *= a[i];
}
int products_above[N];
p = 1;
for (int i = N - 1; i >= 0; --i) {
products_above[i] = p;
p *= a[i];
}
int products[N]; // This is the result
for (int i = 0; i < N; ++i) {
products[i] = products_below[i] * products_above[i];
}
如果你也需要空间中的解是O(1)，你可以这样做(在我看来不太清楚):
int a[N] // This is the input
int products[N];
// Get the products below the current index
int p = 1;
for (int i = 0; i < N; ++i) {
products[i] = p;
p *= a[i];
}
// Get the products above the current index
p = 1;
for (int i = N - 1; i >= 0; --i) {
products[i] *= p;
p *= a[i];
}
