Java乘积题举例分析

本篇内容介绍了“Java乘积题举例分析”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

创新互联公司网站建设公司一直秉承“诚信做人,踏实做事”的原则,不欺瞒客户,是我们最起码的底线! 以服务为基础,以质量求生存,以技术求发展,成交一个客户多一个朋友!专注中小微企业官网定制,网站制作、成都网站建设,塑造企业网络形象打造互联网企业效应。

面试题:颠倒乾坤

在一棵二叉搜索树中,有两个节点颠倒了顺序。要求实现一个算法,在不改变树结构的前提下,恢复正确的二叉搜索树。给出一个空间为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

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

“Java乘积题举例分析”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!


网页题目:Java乘积题举例分析
新闻来源:http://scyanting.com/article/jjpppp.html