我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
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);
}
其他回答
最近有人问我这个问题，虽然我不能得到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]
还有一个O(N^(3/2))非最优解。不过，这很有趣。
首先预处理大小为N^0.5的每个部分乘法(这在O(N)时间复杂度中完成)。然后，计算每个数字的其他值的倍数可以在2*O(N^0.5)时间内完成(为什么?因为您只需要将其他((N^0.5) - 1)数字的最后一个元素相乘，并将结果与属于当前数字组的((N^0.5) - 1)数字相乘。对每一个数都这样做，可以得到O(N^(3/2))时间。
例子:
4, 6, 7, 2, 3, 1, 9, 5, 8
部分结果: 4*6*7 = 168 2*3*1 = 6 9*5*8 = 360
要计算3的值，需要将其他组的值乘以168*360，然后乘以2*1。
我有一个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;
}
这是O(n²)但f#太漂亮了
List.fold (fun seed i -> List.mapi (fun j x -> if i=j+1 then x else x*i) seed)
[1;1;1;1;1]
[1..5]
我们正在分解数组的元素，首先从下标之前开始，即前缀，然后是下标或后缀之后
class Solution:
def productExceptSelf(nums):
length = len(nums)
result = [1] * length
prefix_product = 1
postfix_product = 1
# we initialize the result and products
for i in range(length)
result[i] *= prefix_product
prefix_product *= nums[i]
#we multiply the result by each number before the index
for i in range(length-1,-1,-1)
result[i] *= postfix_product
postfix_product *= nums[i]
#same for after index
return result
抱歉，走路时用手机
