这个问题已经在这里有了答案:
11 年前关闭。
我遇到了一个真正让我思考的面试任务/问题......所以它是这样的:
您有一个由 N 个数字组成的数组 A[N]。您必须组成一个数组Output [N],以便Output [i]等于A [N]除A [i]以外的所有元素的乘法。例如,Output [0]将是A [1]与A [N-1]的乘积,而Output [1]将是A [0]与A [2]与A [N-1]的乘积。在没有除法运算符和 O(n) 的情况下解决它。
我真的试图想出一个解决方案,但我总是以 O(n^2) 的复杂性结束。也许谁能比我更聪明,谁能告诉我一种适用于O(n)的算法,或者至少给我一个提示...
最佳答案
构造两个临时数组 - B[N] 和 C[N]。将 B[N] 的每个元素作为其左侧的 A[N] 元素(包括其自身)的乘积 - 从左到右工作,N 次操作。将C [N]的每个元素形成为右边的A [N]元素(包括自身)的乘积-从右到左,进行N个运算。
然后 A[n] = B[n-1] * C[n+1] - 另一个 N 操作来解决这个问题。你最终只需要 3N 次操作,即 O(N)。它只是很短,因为 B[0] 和 C[N-1],以及第一个和最后一个 A,不需要乘法。另外,C[0] = B[N-1],所以我认为你应该正好需要 3N-5 次操作。
关于algorithm - 如何让它在 O(n) 中工作?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/2911022/