题解 | #在二叉树中找到两个节点的最近公共祖先#

public class Solution{ int count = 0; public int InversePairs(int[] array){ if(array.length < 2) return 0; mergeSort(array,0,array.length - 1); return count; } public void mergeSort(int[] array,int left,int right){ int mid = ( left + right )/2; if(left < right){ mergeSort(array,left,mid); mergeSort(array,mid+1,right); merge(array,left,mid,right); } } public void merge(int[] array,int left,int mid,int right){ int[] arr = new int[right - left +1]; int temp = 0; int low = left; int high = mid +1; while(low <= mid && high <= right){ if(array[low] < array[high]){ arr[temp ++] = array[low ++]; }else{ arr[temp ++] = array[high ++]; count += mid - low + 1; count %= 1000000007; } } while(low <= mid){ arr[temp ++] = array[low ++]; } while(high <= right){ arr[temp ++] = array[high++]; } // temp = left; for(int num : arr){ array[left++] = num; } } }