我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
还有一个解决方案，使用除法。有两次遍历。 把所有元素相乘，然后除以每个元素。
其他回答
上下两次。在O(N)完成的工作
private static int[] multiply(int[] numbers) {
int[] multiplied = new int[numbers.length];
int total = 1;
multiplied[0] = 1;
for (int i = 1; i < numbers.length; i++) {
multiplied[i] = numbers[i - 1] * multiplied[i - 1];
}
for (int j = numbers.length - 2; j >= 0; j--) {
total *= numbers[j + 1];
multiplied[j] = total * multiplied[j];
}
return multiplied;
}
ruby的解决方案
a = [1,2,3,4]
result = []
a.each {|x| result.push( (a-[x]).reject(&:zero?).reduce(:*)) }
puts result
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);
}
}
我想出了这个解决方案，我发现它很清楚，你觉得呢!?
下面是Ruby中的一行程序解决方案。
全国矿工工会。映射{|n| (num - [n]).inject(:*)}
我有一个O(n)空间和O(n²)时间复杂度的解，如下所示，
public static int[] findEachElementAsProduct1(final int[] arr) {
int len = arr.length;
// int[] product = new int[len];
// Arrays.fill(product, 1);
int[] product = IntStream.generate(() -> 1).limit(len).toArray();
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (i == j) {
continue;
}
product[i] *= arr[j];
}
}
return product;
}
