我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
下面是Ruby中的一行程序解决方案。
全国矿工工会。映射{|n| (num - [n]).inject(:*)}
其他回答
最近有人问我这个问题，虽然我不能得到O(N)，但我有一个不同的方法(不幸的是O(N²))，但我想无论如何都要分享。
首先转换为列表<Integer>。
遍历原始数组array.length()次。
使用while循环乘下一组所需的数字:
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
然后将res添加到一个新数组(当然，您已经在前面声明了)，然后将数组[i]的值添加到List，依此类推。
我知道这不会有太大的用处，但这是我在面试的压力下想到的:)
int[] array = new int[]{1, 2, 3, 4, 5};
List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
int[] newarray = new int[array.length];
int res = 1;
for (int i = 0; i < array.length; i++) {
int temp = i;
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
newarray[i] = res;
list.add(array[i]);
res = 1;
}
输出:[24,120,60,40,30]
在这里添加我的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;
}
将Michael Anderson的解决方案翻译成Haskell:
otherProducts xs = zipWith (*) below above
where below = scanl (*) 1 $ init xs
above = tail $ scanr (*) 1 xs
以下是线性O(n)时间内的简单Scala版本:
def getProductEff(in:Seq[Int]):Seq[Int] = {
//create a list which has product of every element to the left of this element
val fromLeft = in.foldLeft((1, Seq.empty[Int]))((ac, i) => (i * ac._1, ac._2 :+ ac._1))._2
//create a list which has product of every element to the right of this element, which is the same as the previous step but in reverse
val fromRight = in.reverse.foldLeft((1,Seq.empty[Int]))((ac,i) => (i * ac._1,ac._2 :+ ac._1))._2.reverse
//merge the two list by product at index
in.indices.map(i => fromLeft(i) * fromRight(i))
}
这是可行的，因为本质上答案是一个数组，它是左右所有元素的乘积。
下面是另一个简单的概念，可以解决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));
