我在求职面试中被问到这个问题,我想知道其他人如何解决这个问题 . 我对Java最熟悉,但欢迎使用其他语言的解决方案 .
给定一组数字,nums,返回一组数字产品,其中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)中执行此操作而不使用除法 .
30 回答
这是解决
O(N)
中问题的另一个简单概念 .polygenelubricants方法的解释是:诀窍是构造数组(在4个元素的情况下)
通过分别从左边缘和右边缘开始,可以在O(n)中完成这两个操作 .
然后将两个数组逐个元素相乘,得到所需的结果
我的代码看起来像这样:
如果你需要在太空中是O(1)你也可以这样做(这不太清楚恕我直言)
这是一个小的递归函数(在C中)来进行修改 . 它需要O(n)额外空间(在堆栈上) . 假设数组在a中并且N保持数组长度,我们有
预先计算每个元素左侧和右侧的数字乘积 . 对于每个元素,期望的 Value 是它的neigbors产品的产物 .
结果:
(更新:现在我仔细看看,这使用与Michael Anderson,Daniel Migowski和上面的polygenelubricants相同的方法)
这是我尝试用Java解决它 . 对于非标准格式化抱歉,但代码有很多重复,这是我能做的最好的,使它可读 .
循环不变量是
pi = nums[0] * nums[1] *.. nums[i-1]
和pj = nums[N-1] * nums[N-2] *.. nums[j+1]
. 左侧的i
部分是"prefix"逻辑,右侧的j
部分是"suffix"逻辑 .递归单行
Jasmeet给了一个(漂亮!)递归解决方案;我把它变成了这个(丑陋的)Java单线程 . 它使用堆栈中的
O(N)
临时空间进行就地修改 .将Michael Anderson的解决方案翻译成Haskell:
悄悄地规避“不分裂”规则:
在这里,简单而干净的解决方案具有O(N)复杂性:
C,O(n):
左行 - >正确并继续保存产品 . 称之为过去 . - > O(n)
旅行权 - >左保留产品 . 称之为未来 . - > O(n)
结果[i] =过去[i-1] * future [i 1] - > O(n)
过去[-1] = 1;和未来[n 1] = 1;
上)
这是我在现代C中的解决方案 . 它使用
std::transform
并且很容易记住 .Online code (wandbox).
这是O(n ^ 2)但是f#太漂亮了:
整蛊:
使用以下内容:
是的,我确信我错过了一些i-1而不是我,但这就是解决问题的方法 .
还有一个O(N ^(3/2)) non-optimal 解决方案 . 不过,这很有意思 .
首先预处理大小为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 .
我想出了这个解决方案,我发现它很清楚你怎么想!?
arr = [1,2,3,4,5] prod = [] productify(arr,prod,0)print prod
在这里添加我的JavaScript解决方案,因为我没有找到任何人建议这个 . 什么是除法,除了计算从另一个数字中提取数字的次数?我经历了计算整个数组的乘积,然后迭代每个元素,并将当前元素减去零:
我习惯用C#:
那么,这个解决方案可以被认为是C / C的解决方案 . 假设我们有一个包含n个元素的数组“a”,如[n],那么伪代码如下所示 .
还有一个解决方案,使用除法 . 两次遍历 . 将所有元素相乘,然后开始按每个元素分割 .
这是我的代码:
这是一个使用C#的稍微有用的示例:
我不完全确定这是O(n),由于创建的Funcs的半递归,但我的测试似乎表明它是O(n)及时 .
这里完整的是Scala中的代码:
这将打印出以下内容:
该程序将过滤掉当前的元素(_!=ELEM);并使用reduceLeft方法将新列表相乘 . 如果你使用scala视图或Iterator进行惰性评估,我认为这将是O(n) .
//这是Java中的递归解决方案//从主要产品(a,1,0)调用如下;
O(n)运行时的简洁解决方案:
对于每个元素,计算在此之前出现的所有元素的乘积,并将其存储在数组"pre"中 .
对于每个元素计算在该元素之后出现的所有元素的乘积并将其存储在数组中"post"
为元素i创建最终数组“result”,
我们可以先从列表中排除
nums[j]
(其中j != i
),然后得到其余的产品;以下是解决这个难题的python way
:根据Billz回答 - 抱歉我无法发表评论,但这里有一个正确处理列表中重复项的scala版本,可能是O(n):
收益:
我有一个解决方案,下面提供
O(n)
空间和O(n^2)
时间复杂度,