本篇內(nèi)容介紹了“Java乘積題舉例分析”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

創(chuàng)新互聯(lián)公司網(wǎng)站建設(shè)公司一直秉承“誠信做人，踏實做事”的原則，不欺瞞客戶，是我們最起碼的底線！ 以服務(wù)為基礎(chǔ)，以質(zhì)量求生存，以技術(shù)求發(fā)展，成交一個客戶多一個朋友！專注中小微企業(yè)官網(wǎng)定制，網(wǎng)站制作、成都網(wǎng)站建設(shè)，塑造企業(yè)網(wǎng)絡(luò)形象打造互聯(lián)網(wǎng)企業(yè)效應(yīng)。

面試題：顛倒乾坤

在一棵二叉搜索樹中，有兩個節(jié)點顛倒了順序。要求實現(xiàn)一個算法，在不改變樹結(jié)構(gòu)的前提下，恢復(fù)正確的二叉搜索樹。給出一個空間為O(n)的實現(xiàn)很容易，那該如何給出一個空間O(1)的實現(xiàn)呢？

忘我之乘積分析

題目：

給你一個數(shù)組A[1..n]，請你在O(n)的時間里構(gòu)造一個新的數(shù)組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]計算一遍，總的時間復(fù)雜度為O(n^2)。不符合題目要求，必須減少乘法的次數(shù)。如何減少乘法的次數(shù)呢？ 繼續(xù)分析，通過上面的變換，我們可以得到B[i]是由兩部分相乘得到的：

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

先看***部分，在計算B[i+1]的時候，是可以利用B[i]的***部分結(jié)果的，只需要乘以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]的第二部分。

由此分析，構(gòu)建兩個新的數(shù)組：C和D（為了方便解釋，用了兩個數(shù)組），

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}

構(gòu)建C和D都是O(n)的時間復(fù)雜度（C從前到后遍歷一遍數(shù)組，D從后到前遍歷一邊數(shù)組），然后，B[i] = C[i]*D[i]也是O(n)的時間復(fù)雜度。整體算法的時間復(fù)雜度是O(n)。

題目到這解答完畢。

但是面試官的問題還沒有完，他們會繼續(xù)問，這個解法的空間是O(n)的，能夠空間O(1)的情況下實現(xiàn)么？

首先看看一個只有5個數(shù)的數(shù)組，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乘積題舉例分析”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！

本文標(biāo)題：Java乘積題舉例分析
網(wǎng)站鏈接：http://jinyejixie.com/article38/jjpppp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、企業(yè)網(wǎng)站制作、品牌網(wǎng)站制作、自適應(yīng)網(wǎng)站、ChatGPT、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)