計算排列中「倒位」的數量

設A是大小爲N的數組。我們叫了幾個指標(i,j)的「逆」如果i < j和A[i] > A[j]計算排列中「倒位」的數量

我需要找到接收大小N的數組（具有唯一的編號）算法和返回的時間O(n*log(n))逆數。

2011-06-29 Shai Balassiano

很相似：http://stackoverflow.com/questions/4552591/how-to-find-the-number-of-反轉功能於一個陣列。區別在於，這指定數組包含一個排列，而不是任意值。 –

也相關：[數組倒數]（http://stackoverflow.com/questions/337664/counting-inversions-in-an-array） – PengOne

您可以使用merge sort算法。

在合併算法的循環中，左右兩半均按升序排列，我們希望將它們合併到單個排序數組中。請注意，右側的所有元素都具有比左側更高的索引。

假設array [leftIndex]> array [rightIndex]。這意味着索引爲leftIndex的元素後面的左側部分中的所有元素也都大於右側的當前元素（因爲左側按升序排序）。因此，右側的當前元素生成numberOfElementsInTheLeftSide - leftIndex + 1反演，因此將其添加到您的全局反演計數中。

一旦該算法完成執行，你有你的答案，並在最壞的情況下合併排序是O（n日誌n）。

來源

2011-06-29 16:10:48 IVlad

Cham和Patrascu於2010年在SIAM上發表了一篇題爲Counting Inversions, Offline Orthogonal Range Counting, and Related Problems的文章，它給出了一個採用O（n sqrt（log（n）））時間的算法。這是目前最知名的算法，並改進了長期的O（n log（n）/ log（log（n）））算法。從抽象：

我們給出了n個元素計數置換倒的數量爲O（n開方（LG N）） - 時間算法。此改善的長期結合的先前 爲O（n LG N/LG樂n）的該隨後從迪茨的數據結構 [WADS'89]，和答案的 Andersson和皮特森[SODA'95一個問題]。由於對於相關的動態排名問題，Dietz的結果已知爲最優的，我們的結果顯示離線設置中的顯着改進。

我們的新技術是相當簡單：我們執行特里結構的一個「垂直分區」（類似於貨車昂德博阿斯樹），和從外部存儲器使用的想法。然而，該技術發現衆多應用：例如，我們得到

在d尺寸，一個算法來答案Ñ離線正交範圍計數在時間查詢爲O（n LG ^{d-2 + 1/d} n）;

改進在線數據建設時間結構正交範圍計數;

針對部分總和問題的改進更新時間 ;

更快用於查找軸對齊矩形和斜率選擇問題的最大深度的的Word RAM算法。

作爲獎勵，我們還給出了計數反轉的簡單（1 +ε）近似算法，在線性時間運行，提高了前 爲O（n LG樂n）的界由安德森和彼得森。

來源

2011-06-29 21:44:58 PengOne

我認爲最簡單的方法來做到這一點（那是因爲我喜歡數據結構）是使用binary indexed tree。請注意，如果你需要的只是一個解決方案，那麼合併排序也會起作用（我只是認爲這個概念完全不合邏輯！）。其基本思想是：構建一個更新O（log n）中的值的數據結構，並回答查詢「到目前爲止，數組中已經有多少個小於x的數字？」考慮到這一點，你可以很容易地回答有多少比x更有助於反轉的情況，其中x是該對中的第二個數字。例如，考慮列表{3,4,1,2}。

當處理3時，到目前爲止沒有其他數字，所以倒數3在右側= 0 當處理4時，到目前爲止，小於4的數字數目= 1，因此數目更大的數字反轉）= 0 現在，當處理1時，小於1的數字的數量= 0，這個數目更大的數字= 2，這有助於兩次反轉（3,1）和（4,1）。同樣的邏輯適用於2，它比它少1個數字，因此2比它大。

現在，唯一的問題是瞭解這些更新和查詢如何在日誌n中發生。上面提到的網址是我讀過的最好的教程之一。

來源

2011-06-30 09:47:42 kyun

這些都是原始MERGE和從Cormen，Leiserson，的Rivest，斯坦因算法導論合併排序算法0：

MERGE(A,p,q,r) 
1 n1 = q - p + 1 
2 n2 = r - q 
3 let L[1..n1 + 1] and R[1..n2 + 1] be new arrays 
4 for i = 1 to n1 
5  L[i] = A[p + i - 1] 
6 for j = 1 to n2 
7  R[j] = A[q + j] 
8 L[n1 + 1] = infinity 
9 R[n2 + 1] = infinity 
10 i = 1 
11 j = 1 
12 for k = p to r 
13  if L[i] <= R[j] 
14   A[k] = L[i] 
15   i = i + 1 
16  else A[k] = R[j] 
17   j = j + 1

和

MERGE-SORT(A,p,r) 
1 if p < r 
2  q = floor((p + r)/2) 
3  MERGE-SORT(A,p,q) 
4  MERGE-SORT(A,q + 1,r) 
5  MERGE(A,p,q,r)

在管線8和9中MERGE無窮遠是所謂的哨卡，它具有這樣的價值，所有數組元素都比它小。爲了得到反轉次數，可以引入一個全局計數器假設ninv在調用MERGE-SORT 之前初始化爲零，並且在第16行後面的else語句中添加一行來修改MERGE算法，例如

ninv += n1 - i

比合並排序完成後NINV將持有逆轉的次數

來源

2017-05-22 15:23:12 baz

計算排列中「倒位」的數量

回答

相關問題