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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
let countReverse = 0;//累加
const kmod = 1000000007;
function InversePairs (data) {
	mergeSort(data);
	console.log('countReverse----', countReverse);
	return countReverse;
}
function mergeSort (data, len = data.length) {
	let mid = Math.floor((len - 1) / 2)//中位数
	if (len <= 1) {//出递归
		return data
	}
	let left = mergeSort(data.slice(0, mid + 1))
	let right = mergeSort(data.slice(mid + 1, len))
	let res = mergeOrderly(left, right)
	return res
}

function mergeOrderly (left, right) {
	let i = 0
	let j = 0
	let container = []
	while (i < left.length && j < right.length) {
		if (left[i] > right[j]) {//如果左边大于右边，则是逆序对
			countReverse += left.length - i//累加之后所有的数量，因为已经排序好了
			countReverse = countReverse % kmod
			container.push(right[j])
			j++
		} else {
			container.push(left[i])
			i++
		}
	}

	if (i < left.length) {
		container = container.concat(left.slice(i, left.length))
	} else {
		container = container.concat(right.slice(j, right.length))
	}
	return container
}


module.exports = {
    InversePairs : InversePairs
};


module.exports = {
    InversePairs : InversePairs
};