益智..将数组X值的求解产品 [英] Puzzle.. solving product of values in array X

问题描述

能否请你帮我解决这个吗？

Can you please help me solving this one?

您有n个整数的无序排列的X.查找包含n个元素，其中Mi为x中所有整数除曦的产品列M。您不得使用部门。您可以使用额外的内存。 （提示：有解决方案比为O（n ^ 2）速度更快。）

You have an unordered array X of n integers. Find the array M containing n elements where Mi is the product of all integers in X except for Xi. You may not use division. You can use extra memory. (Hint: There are solutions faster than O(n^2).)

基本的 - 为O（n ^ 2）和一个用除法是很容易。但我就是不能得到另一种解决方案是为O快（N ^ 2）。

The basic ones - O(n^2) and one using division is easy. But I just can't get another solution that is faster than O(n^2).

推荐答案

让离开[I] 在 X <所有元素的产品/从 1..i >。让右键[I] 是所有元素中的 X中的产品从 i..N 。你可以计算无论是在 O（N）不按以下方式划分：离开[我] =左[我 - 1] * X [我] 和右键[I] =正确的[I + 1] * X [I] ;

Let left[i] be the product of all elements in X from 1..i. Let right[i] be the product of all elements in X from i..N. You can compute both in O(n) without division in the following way: left[i] = left[i - 1] * X[i] and right[i] = right[i + 1] * X[i];

现在，我们将计算 M ： M [I] =左[我 - 1] *正确的[I + 1]

注：离开和右键是数组

希望这是明确的：）

这篇关于益智..将数组X值的求解产品的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！