P134 重要逆序对

描述#

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

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

代码#

public class AlgoCasts {

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

  private void merge(int[] arr, int low, int mid, int high, int[] tmp) {
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
      if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
      else 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);
  }

  private int count(int[] arr, int low, int mid, int high) {
    int i = low, j = mid + 1, cnt = 0;
    while (i <= mid && j <= high) {
      if (arr[i] <= 2L * arr[j]) {
        ++i;
      } else {
        cnt += (mid - i + 1);
        ++j;
      }
    }
    return cnt;
  }

  private int sortAndCount(int[] arr, int low, int high, int[] tmp) {
    int 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 += count(arr, low, mid, high);
      merge(arr, low, mid, high, tmp);
    }
    return cnt;
  }

  // Time: O(n*log(n)), Space: O(n)
  public int 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);
  }

}