eve*_*ean 4 algorithm complexity-theory
我遇到了一个真正让我思考的面试任务/问题......所以在这里:
你有一个数字A [N]的N个数字.你必须组成一个数组Output [N],使得Output [i]将等于除A [i]之外的所有A [N]元素的乘法.例如,Output [0]将A [1]乘以A [N-1],Output [1]将乘以A [0]和A [2]乘以A [N-1].无需除法运算符和O(n)求解.
我真的试图提出一个解决方案,但我总是以O(n ^ 2)的复杂性结束.或许比我更聪明的人可以告诉我一个在O(n)中工作的算法,或者至少给我一个提示......
Dav*_*d M 15
构造两个临时数组--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次操作.