牛客网: BM20
题目: 求出数组中逆序对总数
思路: 使用归并排序思路,先分裂,再合并,合并的时候,左半段有序,右半段有序,如果左半段某个值大于右半段某个值 data[i] > data[j], 则可通过j与右半段起始坐标之间的距离算出共有多少个比data[i]小,即这一小段的逆序对的数量;在复制数组dataCopy中一直按照比较的结果来更新数值,作为回溯时的data使用。
注意: 中间点 mid = (left+right)/2,需要归到左半段中,否则递归时使用inverse(left, mid-1), 即下一层right=mid-1, 存在right < left情况,如果这样的话,则需要在递归前添加判断单独处理,否则会栈溢出。
代码:
package main
// import "fmt"
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
const BASE = 1000000007
func InversePairsCount(data, dataCopy []int, left, right int) int {
if left < right {
mid := left + (right - left) >> 1
leftCount := InversePairsCount(dataCopy, data, left, mid)
rightCount := InversePairsCount(dataCopy, data, mid+1, right)
count := 0
i := mid
j := right
idx := right
for i >= left && j > mid {
if data[i] > data[j] {
count += j - mid
dataCopy[idx] = data[i]
idx--
i--
} else {
dataCopy[idx] = data[j]
idx--
j--
}
}
for i >= left {
dataCopy[idx] = data[i]
idx--
i--
}
for j > mid {
dataCopy[idx] = data[j]
idx--
j--
}
return (count + leftCount + rightCount) % BASE
} else{
dataCopy[left] = data[left]
return 0
}
}
func InversePairs( nums []int ) int {
// write code here
if len(nums) == 0 {
return 0
}
dataCopy := make([]int, len(nums))
for i := 0; i < len(nums); i++ {
dataCopy[i] = nums[i]
}
left, right := 0, len(nums) - 1
count := InversePairsCount(nums, dataCopy, left, right)
return count % BASE
}