剑指 Offer 51. 数组中的逆序对

题目链接： 剑指 Offer 51. 数组中的逆序对

题目描述：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

解法思路：

代码：
暴力做法：

func reversePairs(nums []int) int {
    var res int
    n := len(nums)
    if n == 0 {
        return res
    }
    for i :=0 ;i < n;i++{
        for j:=i+1;j <n;j++{
            if nums[j]<nums[i]{
                res++
            }
            
        }
    }
    return res
}

采用归并排序的思想：

func reversePairs(nums []int) int {
    
    return merge(nums, 0, len(nums) - 1)
}

func merge(nums []int, l, r int) int {
    //递归的退出条件
    if l >= r {
        return 0
    }
    mid := (l + r) >> 1
    // 递归处理左边和右边
    res := merge(nums, l, mid) + merge(nums, mid+1, r)

    //单层递归的逻辑
    var tmp []int
    i, j := l , mid+1
    for i <= mid && j <= r {
        if nums[i] <= nums[j] {  //如果左边的比右边的小，正常放入合并后的tmp数组
            tmp = append(tmp,nums[i])
            i++
        } else { // 否则右边比左边小，则存在逆序对，逆序对的数量是 mid -i +1
            res += mid - i + 1
            tmp = append(tmp,nums[j])  //将右边的放入tmp
            j++
        }
    }
    // 将剩余的未处理的数，直接加入到tmp中
    for i <= mid {
        tmp = append(tmp,nums[i])
        i++
    }
    for j <= r {
        tmp = append(tmp,nums[j])
        j++
    }
    //最后这里，将合并后的数组，接到原数组的l的后面
    for i,v := range tmp {
        nums[l+i] = v
    }
    return res
}