数组中的逆序对

发表于 | 分类于

题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
并将P对1000000007取模的结果输出。 即输出P%1000000007

思路

归并排序的思路

先把数组分隔成子数组， 先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。
在统计逆序对的过程中，还需要对数组进行排序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function InversePairs(data) {
  if (!data || data.length < 2) return 0;
  const copy = data.slice();
  let count = 0;
  count = mergeCount(data, copy, 0, data.length - 1);
  return count % 1000000007;
}
function mergeCount(data, copy, start, end) {
  if (start === end) return 0;
  const mid = end - start >> 1,
    left = mergeCount(copy, data, start, start + mid), // 注意参数，copy作为data传入
    right = mergeCount(copy, data, start + mid + 1, end); // 注意参数，copy作为data传入
  let [p, q, count, copyIndex] = [start + mid, end, 0, end];
  while (p >= start && q >= start + mid + 1) {
    if (data[p] > data[q]) {
      copy[copyIndex--] = data[p--];
      count = count + q - start - mid;
    } else {
      copy[copyIndex--] = data[q--];
    }
  }
  while (p >= start) {
    copy[copyIndex--] = data[p--];
  }
  while (q >= start + mid + 1) {
    copy[copyIndex--] = data[q--];
  }
  return count + left + right;
}