题解 | #数组中的逆序对#

function InversePairs(data)
{
    // write code here
  if(data.length < 2) return 0
  const copy = [...data]
  const result = mergeSort(data, copy, 0, data.length - 1) % 1000000007
  return result
}

function mergeSort(data, copy, left, right) {
  if(left === right) {
    copy[left] = data[right]
    return 0
  }
  let count = 0
  const mid = Math.floor((left + right) / 2)
  count += mergeSort(copy, data, left, mid)
  count += mergeSort(copy, data, mid + 1, right)
  let [i, j, k] = [mid, right, right]
  while(i >= left && j >= mid + 1) {
    if(data[i] > data[j]) {
      copy[k--] = data[i--]
      count += j - mid
    } else {
      copy[k--] = data[j--]
    }
  }
  while(i >= left) copy[k--] = data[i--]
  while(j >= mid + 1) copy[k--] = data[j--]
  return count
}

module.exports = {
    InversePairs : InversePairs
};

抄于排行榜中