題目描述
在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字斑响，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)α馐簟］斎胍粋€(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)舰罚∨γ牛——?jiǎng)χ竜ffer
分析：一般求總數(shù)，全部可能的種樹的題型基本都是用遞歸营罢，回溯赏陵。
算法考察：歸并排序
這道題使用一個(gè)額外空間目的是將所有數(shù)字排序成有序狀態(tài)，同時(shí)分解子問題饲漾，對相鄰坐標(biāo)的數(shù)進(jìn)行對比蝙搔，記下是否逆序。之后將其排序放入下一次父問題的比較之中并且不會(huì)重復(fù)計(jì)數(shù)考传。
例如：1 2 1 2 1吃型，將其分成 A 1 2 1和 B 2 1兩個(gè)子問題，A的解為1并變成112僚楞，B的解為1變成12勤晚，求解子問題之后再從各自的最末端使用標(biāo)記進(jìn)行逐一對比。一旦A中標(biāo)記比B中標(biāo)記大（比如A中2比B中1大）泉褐，且兩者都是有序的赐写，因此A標(biāo)記下的數(shù)，大于所有后者數(shù)組標(biāo)記之前的所有數(shù)（包括該標(biāo)記數(shù)）膜赃。直接算出此次歸并排序的逆序總數(shù)血淌。
//test case, should return 3
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {1,2,1,2,1};
System.out.println(solution.getPairs(arr));
}
public int getPairs(int [] array) {
if (array.length <= 1) {
return array.length;
}
int[] arrayCopy = new int[array.length];
for (int i = 0; i < arrayCopy.length; i++) {
arrayCopy[i] = array[i];
}
int count = getPairsCount(array,arrayCopy,0,array.length-1);
return count;
}
public int getPairsCount(int[] array, int[] arraycopy,int start,int end) {
if (start == end) {
arraycopy[start] = array[start];
return 0;
}
int mid = (end-start)/2;
// 這個(gè)遞歸，注意參數(shù)中兩個(gè)數(shù)組的位置變化财剖，每次都是對需要進(jìn)行歸并的那個(gè)數(shù)組進(jìn)行處理
int left = getPairsCount(arraycopy, array, start, start+mid);
int right = getPairsCount(arraycopy, array, start+mid+1, end);
int count = 0;
int index = end;
int i = start+mid;
int j = end;
while (i >= start && j >= start+mid+1) {
if (array[i] > array[j]) {
arraycopy[index--] = array[i--];
count += j - (start+mid);
}
else {
arraycopy[index--] = array[j--];
}
}
for(;i >= start;--i){
arraycopy[index--] = array[i];
}
for(; j >= start + mid +1; --j){
arraycopy[index--] = array[j];
}
return count+left+right;
}
}
