LCR 170. 交易逆序对的总数

LCR 170. 交易逆序对的总数

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

---

归并，我去，上一次写这个逆序对还是去年10月份，现在竟然还记得。。

func reversePairs(record []int) int {
    return MergesSort(record, 0, len(record) - 1)
}


func MergesSort(record []int, left, right int) int {
    if left >= right {
        return 0
    }
    ans := 0
    mid := (left + right) / 2
    //统计子数组的逆序对
    ans += MergesSort(record, left, mid) + MergesSort(record, mid + 1, right)
    i, j := left, mid + 1
    var tmp []int
    for i <= mid && j <= right {
        if record[i] <= record[j] {
            tmp = append(tmp, record[i])
            //增加逆序对数量
            //这说明此前加入的右侧的元素
            //一定小于当前加入的元素(这个元素在左侧)
            ans += j - (mid + 1)
            i++
        } else {
            tmp = append(tmp, record[j])
            j++
        }
    }
    for ; i <= mid; i++ {
        tmp = append(tmp, record[i])
        ans += right - (mid + 1) + 1
    }
    for ; j <= right; j++ {
        tmp = append(tmp, record[j])
    }
    for i := 0; i < len(tmp); i ++ {
        record[i + left] = tmp[i]
    }
    return ans
}