数组中的逆序对

Question

逆序对是指在一个数组中，如果一个元素大于它后面的元素，则这两个元素组成一个逆序对。要统计一个数组中的逆序对的个数，可以使用分治法。

具体的做法如下：

1. 将数组分为两个子数组，分别在左边子数组和右边子数组中统计逆序对的个数。
2. 将左边子数组和右边子数组分别排序。
3. 统计左边子数组和右边子数组中的逆序对的个数。
4. 将左边子数组和右边子数组合并成一个有序的数组。
5. 返回左边子数组、右边子数组和合并后的数组中的逆序对的个数之和。

以下是逆序对个数的计算的 Java 代码示例：

public class Solution {
    public int inversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int count = mergeSort(nums, 0, nums.length - 1);
        return count;
    }

    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int count = 0;
        count += mergeSort(nums, left, mid);
        count += mergeSort(nums, mid + 1, right);
        count += merge(nums, left, mid, right);
        return count;
    }

    private int merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        int count = 0;
        while (i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                count += mid - i + 1;
                temp[k++] = nums[j++];
            } else {
                temp[k++] = nums[i++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        for (int m = 0; m < temp.length; m++) {
            nums[left + m] = temp[m];
        }
        return count;
    }
}

以上代码使用了归并排序的思想，在归并的过程中统计逆序对的个数并且合并排序后的子数组。时间复杂度为 O(nlogn)。

---

• 使用归并排序的方法来完成
• 每一次涉及到移动就一定是存在逆序对

public class Solution {
  int cnt;
 
  public int InversePairs(int[] array) {
    cnt = 0;
    if (array != null)
      mergeSortUp2Down(array, 0, array.length - 1);
    return cnt;
  }
 
  /*
   * 归并排序（从上往下)
   */
  public void mergeSortUp2Down(int[] a, int start, int end) {
    if (start >= end)
      return;
    int mid = (start + end) >> 1;
 
    mergeSortUp2Down(a, start, mid);
    mergeSortUp2Down(a, mid + 1, end);
 
    merge(a, start, mid, end);
  }
 
  /*
   * 将一个数组中的两个相邻有序区间合并成一个
   */
  public void merge(int[] a, int start, int mid, int end) {
    int[] tmp = new int[end - start + 1];
 
    int i = start, j = mid + 1, k = 0;
    while (i <= mid && j <= end) {
      if (a[i] <= a[j])
        tmp[k++] = a[i++];
      else {
        tmp[k++] = a[j++];
        cnt += mid - i + 1;  // core code, calculate InversePairs............
        cnt %= 1000000007;
      }
    }
 
    while (i <= mid)
      tmp[k++] = a[i++];
    while (j <= end)
      tmp[k++] = a[j++];
    for (k = 0; k < tmp.length; k++)
      a[start + k] = tmp[k];
  }
}