逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对。

暴力解法 #

public int comparator(int[] arr) {
  int ans = 0;
  for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j])
        ans++;
    }
  }
  return ans;
}

归并排序批量计算 #

public int ReverPairNumber(int[] arr) {
  if (arr == null || arr.length < 0)
    return 0;
  return process(arr, 0, arr.length - 1);
}

private int process(int[] arr, int l, int r) {
  if (l == r)
    return 0;

  int mid = l + ((r - l) >> 1);
  return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
}

private int merge(int[] arr, int l, int mid, int r) {
  int[] help = new int[r - l + 1];
  int i = help.length - 1, p1 = mid, p2 = r, res = 0;
  while (p1 >= l && p2 >= mid) {
    res += arr[p1] > arr[p2] ? (p2 - mid) : 0;
    help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
  }

  while (p1 >= l)
    help[i--] = arr[p1--];
  while (p2 > mid)
    help[i--] = arr[p2--];

  for (i = 0; i < help.length; i++)
    arr[l + i] = help[i];

  return res;
}