描述

解題思路：歸并排序
分治：分治即“分而治之”，“分”指的是將一個大而復(fù)雜的問題劃分成多個性質(zhì)相同但是規(guī)模更小的子問題，子問題繼續(xù)按照這樣劃分，直到問題可以被輕易解決；“治”指的是將子問題單獨進(jìn)行處理。經(jīng)過分治后的子問題，需要將解進(jìn)行合并才能得到原問題的解，因此整個分治過程經(jīng)常用遞歸來實現(xiàn)。

具體做法：
1、這里要借助一個輔助數(shù)組，用來暫時存儲合并后的結(jié)果。然后就開始進(jìn)入劃分階段，把原數(shù)組從中間分開，直到子數(shù)組長度為1。
2、使用歸并排序?qū)υ瓟?shù)組進(jìn)行排序，并且統(tǒng)計逆序?qū)?#xff0c;在這里設(shè)置兩個指針i,j分別在左右子區(qū)間上移動，此時左區(qū)間的下標(biāo)i都是小于右區(qū)間的，若知道了第一個大于a[j]的數(shù)，設(shè)為a[i],則左區(qū)間中a[i]以后的所有數(shù)，都比a[j]大。故此時，在左區(qū)間中，與a[j]構(gòu)成逆序?qū)Φ臄?shù)字個數(shù)為左邊剩下的數(shù)，剩余的數(shù)=（右端-左端+1）=（mid-i+1）。這個就是逆序?qū)Φ挠嬎惴椒ā?br /> 3、將排好序的子序列合并，同時累加逆序?qū)Α?/p>

圖解：

代碼：

import java.util.*;public class Solution {/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可** * @param nums int整型一維數(shù)組 * @return int整型*/public int mod = 1000000007;public int mergeSort(int left,int right,int [] data,int[] temp){if(left>=right){return 0;}int mid = (left+right)/2;int res = mergeSort(left,mid,data,temp)+mergeSort(mid+1,right,data,temp);res %= mod;//i,j代表兩個指針，分別在左右子區(qū)間上移動。int i = left,j = mid+1;for(int k=left;k<=right;k++){temp[k] = data[k]; //temp為輔助數(shù)組}for(int k=left;k<=right;k++){if(i==mid+1){  //如果左邊有剩余，不太懂這處代碼data[k] = temp[j++];}//如果右邊有剩余，或者左邊數(shù)更小else if(j==right+1||temp[i]<=temp[j]){ data[k] = temp[i++];//不太懂處代碼}else{data[k] = temp[j++];//逆序?qū)τ嬎惴椒?/span>res += mid-i+1;}}return res%mod;}public int InversePairs (int[] nums) {// write code hereint n = nums.length;int [] res = new int[n];return mergeSort(0,n-1,nums,res);}
}

個人疑問：不知道有沒有和我一樣的小伙伴，在看這道題的解題思路會有這樣的疑問：為什么可以排序呢？這里題目要求的是在一個已經(jīng)列好的數(shù)組中左邊的數(shù)大于右邊，才被稱為逆序數(shù)，而如果使用歸并排序的話，這個數(shù)組不是都有序了嗎，有序的基礎(chǔ)上找逆序，不是和題目違背了嗎？

經(jīng)過思考，我個人的見解是這樣的，這里歸并排序計算逆序?qū)Φ臄?shù)量和暴力解法不一樣，暴力解法是在一個已有的數(shù)組中，對于每一個數(shù)，都判斷其他的數(shù)是否比該數(shù)大，而遞歸排序，它比較的不是相鄰的兩個數(shù)，而是相鄰的兩個子數(shù)組，我認(rèn)為這是看懂這道題的關(guān)鍵，因為比較的是兩個子數(shù)組，所以在兩個子數(shù)組中已經(jīng)排好序是沒關(guān)系的，因為兩個子數(shù)組的相對順序沒有變，所以如果在左區(qū)間發(fā)現(xiàn)了一個比右區(qū)間大的數(shù)，那么說明左區(qū)間中這個數(shù)以后的數(shù)都會比右區(qū)間大，這是遞歸算法計算的公式。