P133 逆序对

描述#

这个题目说的是，给你一个整数数组 a，如果数组中前面的一个数字大于后面的一个数字，那么这两个数字构成一个逆序对。也就是说，对于下标 i 和 j，如果 i < j 且 a(i) > a(j) ，则 a(i) 和 a(j) 构成一个逆序对。你要计算出数组中逆序对的数量。

比如说，给你的数组 a 是：
8, 2, 4, 1
这个数组中有 5 个逆序对。分别是：
(8, 2),
(8, 4),
(8, 1),
(2, 1),
(4, 1),
于是你要返回 5。
如果给你的数组是：
1, 2, 4, 8
这个数组是递增的，不存在前面的数字大于后面数字的情况，因此逆序对的数量为 0。

代码#

public class AlgoCasts {

  // Time: O(n^2), Space: O(1)
  public long reversePairsBruteForce(int[] nums) {
    if (nums == null || nums.length < 2) return 0;
    long cnt = 0;
    for (int i = 0; i < nums.length; ++i)
      for (int j = i+1; j < nums.length; ++j)
        if (nums[i] > nums[j])
          ++cnt;
    return cnt;
  }

  private long mergeAndCount(int[] arr, int low, int mid, int high, int[] tmp) {
    int i = low, j = mid + 1, k = 0, cnt = 0;
    while (i <= mid && j <= high) {
      if (arr[i] <= arr[j]) {
        tmp[k++] = arr[i++];
      } else {
        cnt += (mid - i + 1);
        tmp[k++] = arr[j++];
      }
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= high) tmp[k++] = arr[j++];
    System.arraycopy(tmp, 0, arr, low, k);
    return cnt;
  }

  private long sortAndCount(int[] arr, int low, int high, int[] tmp) {
    long cnt = 0;
    if (low < high) {
      int mid = low + (high - low) / 2;
      cnt += sortAndCount(arr, low, mid, tmp);
      cnt += sortAndCount(arr, mid + 1, high, tmp);
      cnt += mergeAndCount(arr, low, mid, high, tmp);
    }
    return cnt;
  }

  // Time: O(n*log(n)), Space: O(n)
  public long reversePairsMergeSort(int[] nums) {
    if (nums == null || nums.length < 2) return 0;
    int[] tmp = new int[nums.length];
    return sortAndCount(nums, 0, nums.length - 1, tmp);
  }

}