题解 | #数组中的逆序对#
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
利用归并过程中“合”的局部有序性来统计逆序对
func InversePairs( data []int ) int {
// write code here
_ = mergeSort(data)
return count % 1000000007
}
var count int
func mergeSort(data []int) []int { // 归并排序
if len(data) < 2 {
return data
}
mid := len(data) / 2
l := mergeSort(data[:mid])
r := mergeSort(data[mid:])
return mergeCount(l, r)
}
func mergeCount(l, r []int) (tmp []int) {
var (
i, j = 0, 0
l1, l2 = len(l), len(r)
)
for i < l1 && j < l2 {
if l[i] <= r[j] {
tmp = append(tmp, l[i])
i++
} else {
count += l1-i // 利用局部有序性 如{4,5,6} 与 {1,2}，对于元素1则有3个逆序对
tmp = append(tmp, r[j])
j++
}
}
tmp = append(tmp, l[i:]...)
tmp = append(tmp, r[j:]...)
return tmp
}