顛倒乾坤；及忘我之乘積題的分析
今日面試題：顛倒乾坤
在一棵二叉搜索樹(shù)中，有兩個(gè)節(jié)點(diǎn)顛倒了順序。要求實(shí)現(xiàn)一個(gè)算法，在不改變樹(shù)結(jié)構(gòu)的前提下，恢復(fù)正確的二叉搜索樹(shù)。給出一個(gè)空間為O(n)的實(shí)現(xiàn)很容易，那該如何給出一個(gè)空間O(1)的實(shí)現(xiàn)呢？
忘我之乘積分析
題目：
給你一個(gè)數(shù)組
A[1..n]，請(qǐng)你在O(n)的時(shí)間里構(gòu)造一個(gè)新的數(shù)組B[1..n]，使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法運(yùn)算。
分析：
看到題目，不要緊張，要頭腦清晰，看穿面試官的本意，實(shí)際上，他是用除法公式，但又要求不用除法來(lái)迷惑你。
要求在不使用除法的情況下計(jì)算B[i]=A[0]*…*A[n]/A[i]，簡(jiǎn)單變換一下形式，即可得到B[i]=A[0]*…*A[i-1]*A[i+1]*…*A[n]，一共n-1次乘法。每一個(gè)B[i]計(jì)算一遍，總的時(shí)間復(fù)雜度為O(n^2)。不符合題目要求，必須減少乘法的次數(shù)。如何減少乘法的次數(shù)呢？ 繼續(xù)分析，通過(guò)上面的變換，我們可以得到B[i]是由兩部分相乘得到的：
- A[0]*…*A[i-1]
- A[i+1]*…*A[n]
先看***部分，在計(jì)算B[i+1]的時(shí)候，是可以利用B[i]的***部分結(jié)果的，只需要乘以A[i]即得到B[i+1]的***部分。
第二部分同理，計(jì)算完A[i+1]*…*A[n]，再計(jì)算A[i]*A[i+1]*…*A[n]，只需要乘以A[i]即可。A[i]*A[i+1]*…*A[n]是B[i-1]的第二部分。
由此分析，構(gòu)建兩個(gè)新的數(shù)組：C和D（為了方便解釋，用了兩個(gè)數(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)的時(shí)間復(fù)雜度（C從前到后遍歷一遍數(shù)組，D從后到前遍歷一邊數(shù)組），然后，B[i] = C[i]*D[i]也是O(n)的時(shí)間復(fù)雜度。整體算法的時(shí)間復(fù)雜度是O(n)。
題目到這解答完畢。
但是面試官的問(wèn)題還沒(méi)有完，他們會(huì)繼續(xù)問(wèn)，這個(gè)解法的空間是O(n)的，能夠空間O(1)的情況下實(shí)現(xiàn)么？
首先看看一個(gè)只有5個(gè)數(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], 臨時(shí)變量 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
通過(guò)這個(gè)小的例子，我們得到了算法，然后可以推廣到任意多的元素。這個(gè)是面試中常用的技巧。
大家可以自己嘗試把算法變成代碼。
