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

golang算法架构leetcode技术php 2020-03-23

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

解题思路

1，本题，首先想到的是暴力解法，提交超时

2，于是想到了归并，排序

这个题解假设你已经明白归并排序的原理。

就以arr = [7,5,6,4]这个例子来讲解为什么一遍归并排序就看可以解决逆序对的问题。

按照归并排序的思路，会将arr分解为arrL = [7,5],arrR = [6,4];

继续分解为arrLL = [7], arrLR = [5]; arrRL = [6], arrRR = [4];

自此分解完成。

接下来合并：

假设i为arrLL的数组下标，j为arrLR的数组下标, index为新数组res的下标，初始值都为0

首先arrLL与arrLR合并，因为arrLL[i] > arrLR[j]，

所以可以说明arrLL中7及其之后的所有数字都大于arrLR中的5，

也就是说7及其之后的所有元素都可以与5组成逆序对，

所以此时7及其之后的所有元素个数（leftLen - i）即我们要的逆序对数，需要添加到结果sum中。即sum += leftLen - i

（这也就是此算法高效的地方，一次可以查找到好多次的逆序对数，而且不会重复）

合并之后为arrL=[5,7].

根据上述方法将arrRL和arrRR合并为arrR=[4,6];

现在将arrL和arrR合并为arr：

5 > 4，说明5及其之后的所有元素都能与4组成逆序对；所以sum += （leftLen - i）；

5 < 6，正常排序，不做处理

7 > 6，说明7及其之后的所有元素都能与6组成逆序对；所以sum += （leftLen - i）；

7，正常排序，不作处理

最后sum就是所有逆序对的总个数！

代码实现

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
}

golang

文章转载自golang算法架构leetcode技术php，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

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

评论