有一个整数数组,比方说3,5,7,9.您应该创建另一个数组并填充它,使得第二个数组的第0个位置应该是第一个数组中所有数字的乘积,不包括第0个位置的数字,这意味着它应该是5x7x9(不包括3),索引处的数字第二个阵列中的1个将是3x7x9(不包括5)的乘积.
我想到的第一个答案是有2个for循环,这将导致O(n2)的时间复杂度.后来我想到了这个:
将第一个数组中的所有数字相乘(3x5x7x9),并在填充第二个数组时,我将该产品除以该位置的数字.如果我填充第0个位置则除以3,如果我填充第1个位置则除以5,依此类推.这会降低从O(n2)到O(2n)的复杂性.
但是采访者说不允许分裂.除了在某种数据结构中存储不同的可能倍数并在填充时使用它,我想不出别的.我放弃了,但当被问到答案时,他说他会保留2个向前和向后的多重阵列.当被问及解决方案的空间复杂性问题时,他说可以对其进行优化.
我不确定问题是关于空间还是解决方案本身.由于每个人都提供解决方案,这让我觉得他们不理解面试官的解决方案,所以这里有一个解释:
我们维护两个数组.第一个是原始数组的运行产品.所以元素就是原始数组中i第一个i元素的产物(没有乳胶,但是i第一个条目有价值pi{j=0 to i} j).而第二个数组就是它的反方向,因此ith条目将具有值:pi{j=N-i to N} j.
要构造所需的最终数组,我们只需运行两个数组中的每一个并乘以条目.因此,i次最终阵列中的价值,将是所有条目的产品,这是产品0来i-1的产品时代i+1到N,这是第一个数组的乘积i-1项和第二阵列的i+1条目.
总时间和空间 O(n)