数组中的逆序对

1. 题目描述

输入一个数组,求出这个数组中的逆序对的总数。

例如在数组{7，5，6，4}中，一共存在 5 个逆序对，分别是(7,6), (7, 5), (7,4), (6,4), (5,4)。

2. 思路分析

暴力法的时间复杂度是 O(N^2)。利用归并排序的思路，可以将时间复杂度降低到 O(NlogN)。

比如对于 7、5、6、4 来说，会被分成 5、7 和 4、6 两组。

准备两个指针指向两组最后元素，当左边数组指针的对应元素小于右边指针对应元素，结果可以加上从左指针到右指针之间的元素个数（都是逆序的）。

依次移动指针，直到达到边界。

3. 代码实现

代码最后输出了数组，经过归并，数组已经是有序的了。

/**
 *
 * @param {Array} arr
 * @param {Number} start
 * @param {Number} end
 * @return {Number}
 */
function findInversePairNum(arr, start, end) {
  if (start === end) {
    return 0;
  }

  const copy = new Array(end - start + 1);
  const length = (end - start) >> 1;
  const leftNum = findInversePairNum(arr, start, start + length);
  const rightNum = findInversePairNum(arr, start + length + 1, end);

  let i = start + length, // 左子数组的最后一个下标
    j = end, // 右子数组的最后一个下标
    count = leftNum + rightNum,
    copyIndex = end - start; // copy数组中的最后一个下标

  // 可以参考数据集合：[2, 3, 1, 4]
  for (; i >= start && j >= start + length + 1; ) {
    if (arr[i] > arr[j]) {
      copy[copyIndex--] = arr[i--];
      count += j - start - length;
    } else {
      copy[copyIndex--] = arr[j--];
    }
  }

  for (; i >= start; --i) {
    copy[copyIndex--] = arr[i];
  }

  for (; j >= start + length + 1; --j) {
    copy[copyIndex--] = arr[j];
  }

  // 将排序号的数据放到原数组中
  for (i = 0; i < end - start + 1; ++i) {
    arr[i + start] = copy[i];
  }

  // clear
  copy.length = 0;

  return count;
}

/**
 * 测试代码
 */

const arr = [7, 5, 6, 4];
console.log(findInversePairNum(arr, 0, arr.length - 1)); // output: 5
console.log(arr); // output: [4, 5, 6, 7]

大师兄

1. 题目描述

2. 思路分析

3. 代码实现