golang刷leetcode 技巧（37）数组中的逆序对

输入: [7,5,6,4]
输出: 5

func reversePairs(nums []int) int {
  /*
  sum:=0
  for i:=0;i<len(nums)-1;i++{
       for j:=i+1;j<len(nums);j++{
           if nums[i]>nums[j]{
               sum++
           }
       }
  }
  return sum
  */
  s,_:=mergeSort(nums)
  return s
}

func mergeSort(a []int)(int,[]int){
   if len(a)<2{
       return 0,a
   }
   mid:=len(a)/2
   sl,l:=mergeSort(a[:mid])
   sr,r:=mergeSort(a[mid:])
   s,m:=merge(l,r)
   //fmt.Println(sl,sr,s,l,r,m)
   return sl+sr+s,m
}

func merge(a,b []int)(int,[]int){
 sum:=0
 l:=len(a)
 r:=len(b)
 all:=make([]int,l+r)
 i:=0
 j:=0
 index:=0
 for ;index<l+r;index++{
    if i>=l{
        all[index]=b[j]
        j++
        continue
    }
    if j>=r{
        all[index]=a[i]
        i++
        continue
    }
    if a[i]<=b[j]{
        all[index]=a[i]
        i++
        continue
    }else{
        all[index]=b[j]
        //fmt.Println("***",a[i]<=b[j],a[i],b[j],a,b,i,j,all,index)
        j++
       sum+=l-i
    }
 }
return sum,all
}