题解 | #数组中的逆序对#

public class Solution { static int count = 0; public int InversePairs(int [] array) { // 核心思路是归并排序,与之类似的题目有小和问题 if (array == null && array.length < 2){ return 0; } process(array, 0, array.length - 1); return count; } public static void process(int[] arr, int left, int right){ if (left == right){ return; } int mid = left + (right - left) / 2; process(arr, left, mid); process(arr,mid + 1,right); merge(arr,left,mid,right); } public static void merge(int[] arr, int left, int mid, int right){ int[] help = new int[right - left + 1]; int p1 = left; int p2 = mid + 1; int i = 0; while (p1 <= mid && p2 <= right){ // count += arr[p1] > arr[p2] ? 1: 0; // help[i++] = arr[p1] < arr[p2] ? arr[p1++]: arr[p2++];

        if (arr[p1] <= arr[p2]){
            help[i++] = arr[p1++];

//除arr[p1] > arr[p2]外都与归并排序相同 //当左边大于右边时，左边数组中比arr[p2]大的数共有mid-p1+1个 }else { help[i++] = arr[p2++]; count = (count + mid - p1 + 1) % 1000000007; } } while (p1 <= mid){ help[i++] = arr[p1++]; } while (p2 <= right){ help[i++] = arr[p2++]; } for (int j = 0; j < help.length; j++) { arr[left + j] = help[j]; } } }