我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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 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);
}
}
我想出了这个解决方案，我发现它很清楚，你觉得呢!?
其他回答
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));
预先计算每个元素左右两边数字的乘积。 对于每个元素，期望值都是它相邻元素乘积的乘积。
#include <stdio.h>
unsigned array[5] = { 1,2,3,4,5};
int main(void)
{
unsigned idx;
unsigned left[5]
, right[5];
left[0] = 1;
right[4] = 1;
/* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
left[idx] = left[idx-1] * array[idx-1];
}
/* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
right[idx] = right[idx+1] * array[idx+1];
}
for (idx=0; idx <5 ; idx++) {
printf("[%u] Product(%u*%u) = %u\n"
, idx, left[idx] , right[idx] , left[idx] * right[idx] );
}
return 0;
}
结果:
$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24
(更新:现在我仔细看，这使用与Michael Anderson, Daniel Migowski和上面的聚基因润滑剂相同的方法)
我用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]));
下面是我用现代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 << " ";
}
int[] b = new int[] { 1, 2, 3, 4, 5 };
int j;
for(int i=0;i<b.Length;i++)
{
int prod = 1;
int s = b[i];
for(j=i;j<b.Length-1;j++)
{
prod = prod * b[j + 1];
}
int pos = i;
while(pos!=-1)
{
pos--;
if(pos!=-1)
prod = prod * b[pos];
}
Console.WriteLine("\n Output is {0}",prod);
}
