在軟體開發面試的硬演算法輪次中，我最近被問到這個問題。我能夠使用蠻力/遞回來做到這一點，不確定預期的方法，對此有任何幫助嗎？
給定的排列的陣列
n的數字，計算元組的noumber(i,j,k,l,m)使得i<j<k<l<m和a[i]<a[k]<a[j]<a[m]<a[l]。
我的方法 -> 使用遞回嘗試從給定陣列中的所有元組 (i,j,k,l,m) 中的每一個，并只考慮那些滿足條件的元組，比如 N 選擇 5 ，因為這有指數時間復雜性，我想讓它變成三次方或者二次方
uj5u.com熱心網友回復：
我會大量使用四叉樹之類的東西。四叉樹允許您在 2d 中放置一堆點，然后有效地對區域進行搜索。要么找到點，要么只是計算它們。（存盤每個節點中的點數，然后計數會變得更快，因為當您在所需區域中完全有一個正方形時，您可以停止。）
一個有用的四叉樹是將排列視為一系列 n 點(i, a[i])。我們可以使用它來查找i在一個范圍內和a[i]在另一個范圍內的所有情況。叫那棵樹perm。
第二個有用的四叉樹是映射所有的反演i < j和a[j] < a[i]點(i, a[j])。叫那棵樹invert。
現在您的搜索如下所示：
search invert to find all inversions (j, k):
x = count i < j with a[i] < a[k] (search perm)
y = count inversions (l, m) with k < l and a[j] < a[m] (search invert)
add x*y to total
我相信，填充perm需要時間O(n log(n))，填充invert需要O(n^2 log(n))，而每個搜索，獲得的計數應該是這樣的O((log(n))^2)。（不確定那個。）由于存在O(n^2)倒置，因此總性能應該類似于O((n log(n))^2).
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/362048.html