颠倒乾坤；及忘我之乘积题的分析

今日面试题：颠倒乾坤

创新互联是专业的衡阳网站建设公司，衡阳接单;提供网站设计、成都做网站,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行衡阳网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

在一棵二叉搜索树中，有两个节点颠倒了顺序。要求实现一个算法，在不改变树结构的前提下，恢复正确的二叉搜索树。给出一个空间为O(n)的实现很容易，那该如何给出一个空间O(1)的实现呢？

忘我之乘积分析

题目：

给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。

分析：

看到题目，不要紧张，要头脑清晰，看穿面试官的本意，实际上，他是用除法公式，但又要求不用除法来迷惑你。

要求在不使用除法的情况下计算B[i]=A[0]*…*A[n]/A[i]，简单变换一下形式，即可得到B[i]=A[0]*…*A[i-1]*A[i+1]*…*A[n]，一共n-1次乘法。每一个B[i]计算一遍，总的时间复杂度为O(n^2)。不符合题目要求，必须减少乘法的次数。如何减少乘法的次数呢？ 继续分析，通过上面的变换，我们可以得到B[i]是由两部分相乘得到的：

 
 
 

  
  
  
A[0]*…*A[i-1]  
  
  
  
A[i+1]*…*A[n]
 
 
 

先看***部分，在计算B[i+1]的时候，是可以利用B[i]的***部分结果的，只需要乘以A[i]即得到B[i+1]的***部分。

第二部分同理，计算完A[i+1]*…*A[n]，再计算A[i]*A[i+1]*…*A[n]，只需要乘以A[i]即可。A[i]*A[i+1]*…*A[n]是B[i-1]的第二部分。

由此分析，构建两个新的数组：C和D（为了方便解释，用了两个数组），

 
 
 

  
  
  
C[i] = A[0]*…*A[i-1] = C[i-1]*A[i-1]  
  
  
  
D[i] = A[i+1]*…*A[n] = D[i+1]*A[i+1}  
 
 
 

构建C和D都是O(n)的时间复杂度（C从前到后遍历一遍数组，D从后到前遍历一边数组），然后，B[i] = C[i]*D[i]也是O(n)的时间复杂度。整体算法的时间复杂度是O(n)。

题目到这解答完毕。

但是面试官的问题还没有完，他们会继续问，这个解法的空间是O(n)的，能够空间O(1)的情况下实现么？

首先看看一个只有5个数的数组，A[1]，A[2]，A[3]，A[4]，A[5]。

首先从头到尾遍历：

 
 
 

  
  
  
B[1] = A[1]
  
  
  
B[2] = B[1]*A[2]
  
  
  
B[3] = B[2]*A[3]
  
  
  
B[4] = B[3]*A[4]
  
  
  
B[5] = B[4], 临时变量 C=A[5]
 
 
 

然后从尾到头遍历：

 
 
 

  
  
  
B[4] = B[3]*C, C=C*A[4]
  
  
  
B[3] = B[2]*C, C=C*A[3]
  
  
  
B[2] = B[1]*C, C=C*A[2]
  
  
  
B[1] = C
 
 
 

通过这个小的例子，我们得到了算法，然后可以推广到任意多的元素。这个是面试中常用的技巧。

大家可以自己尝试把算法变成代码。

网页题目：颠倒乾坤；及忘我之乘积题的分析
当前路径：http://www.hantingmc.com/qtweb/news29/139479.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联