生活随笔
收集整理的這篇文章主要介紹了
数据结构与算法--数组中的逆序对
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
-
題目：在數組中的兩個數字如果簽名一個數字大于后面的數組，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。
-
案例：輸入數組{7,5，6,4}中一共有5個逆序對分別是{7,6}，{7,5}，{7,4}，{6,4}，{5,4}
-
如上題描述，最簡單的方案就是雙循環遍歷整個數組，掃描第一個數字的時候讓他與其他數字逐個比較，記錄下比他小的數字并且累加一，這個類似冒泡排序的一個算法
-
雙循環的方案時間復雜度與冒泡排序是一樣的都是O(n2)，應該有更快的方案
-
方案二：
- 還是用{7,5，6,4}作為案例分析，既然我們不能拿到第一個后與后面列表逐個比較，那么我們拆解開看能否得到更優方案
- 我們將數組按從左到右拆解成一個元素一個元素的單個數組
- 接著一遍合并相鄰的子數組，一遍統計逆序對的數目
- 我們用如下圖解
-
第一步，我們將數組每次拆解一半，知道數組只剩下1 個或者2個，我們此處用最好理解的方案，拆解成獨立的一個
-
第二步，逐個比較相鄰的，7 < 5 是一個逆序對，我們應該count +1，并且將兩個獨立數組合并成一個有序數組，同理6與4 也是一樣，得到兩個數組，分別是{7,5}， {6,4}
-
第三部接著合并得到的兩個數組，并統計，如下圖中，當left指針指向7 ，right指向6 此時left > right,
-
因為此時兩個數組都是順序的，那么left指向的數據比 第二個數組中所有數都要大
-
那么count疊加次數應該是第二個數組的長度，或者說是right指向的數據的下標大小+1
-
接著移動left，right，并且將較大的數放入合并的數組中
-
如上步驟和我們先進行拆解，然后對子數組逐個進行統計排序的方式和我們之前 文章：數據結構與算法–排序算法總結（動圖演示） 講到的歸并排序的思想是一樣的
-
只不過我們之前的實現中歸并排序拆解的時候選擇的是拆解成2 個，因為這樣可減少遞歸的次數
-
此時我們選擇拆解成1個，是因為我們目的是需要統計次數，如果拆解成2個，必須在對這兩個進行單獨排序的時候單獨統計，這樣多了多余的邏輯
-
經如上分析有如下代碼：
public class InversePairs {public static Integer countInverse
= 0;public static Integer[] mergeSortFindPairs(Integer[] array
){if(array
== null || array
.length
<= 1){return array
;}if(array
.length
< 2){return array
;}Integer middle
= array
.length
/2;Integer[] left
= Arrays.copyOfRange(array
, 0, middle
);Integer[] right
= Arrays.copyOfRange(array
, middle
, array
.length
);return merge(mergeSortFindPairs(left
), mergeSortFindPairs(right
));}public static Integer[] merge(Integer[] left
, Integer[] right
){Integer[] mergeArray
= new Integer[left
.length
+ right
.length
];Integer targetPosition
= mergeArray
.length
-1;Integer leftPosition
= left
.length
-1;Integer rightPosition
= right
.length
-1;while (targetPosition
>= 0){if(leftPosition
>=0 && rightPosition
>= 0){if(left
[leftPosition
] > right
[rightPosition
]){countInverse
+=(rightPosition
+1);mergeArray
[targetPosition
--] = left
[leftPosition
--];}else {mergeArray
[targetPosition
--] = right
[rightPosition
--];}}else {if(leftPosition
< 0){while (rightPosition
>= 0){mergeArray
[targetPosition
--] = right
[rightPosition
--];}}else {while (leftPosition
>= 0){mergeArray
[targetPosition
--] = left
[leftPosition
--];}}}}return mergeArray
;}public static void main(String[] args
) {Integer[] array
= {1,3,44,22,31,4,0,32,14,16,32,9,4,7,23,555,12,123,456};array
= mergeSortFindPairs(array
);for (int i
= 0; i
< array
.length
; i
++) {System.out
.println(array
[i
]);}System.out
.println(countInverse
);}
}
- 如上算法中與歸并算法一樣時間復雜度是O(nlogn)，比最直觀的方案一O(n2)要快，但是我們需要額外一個長度為n的數組，空間復雜度是O(n)，我們用空間換時間的算法。
上一篇：數據結構與算法–第一個只出現一次的字符
下一篇：數據結構與算法–兩個鏈表中第一個公共節點
總結
以上是生活随笔為你收集整理的数据结构与算法--数组中的逆序对的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
