分享merge sort妙用的两题

lc315: https://leetcode.com/problems/co ... numbers-after-self/
lc406: https://leetcode.com/problems/queue-reconstruction-by-height/
这两题均可以用merge sort来实现最优解，虽然真的挺难理解的。主要是在merge sort的merge过程中对于左边array中的的每个元素，有多少个右边array的元素比左边那个元素小，然后可以形象的把右边元素放入result array的过程看成右边小的元素跳跃到左边元素之前，然后根据多少个元素跳过左边的元素来解题。315帖子里有更多关于这个解法的讨论，406这个解法就显得更隐晦了。

全都是数组中求inversion的变种 本质上是利用merge two sorted array的时候 两个array的指针指向较大那个元素的会停下来等指向较小的那个 从等待的时间就可以计算inversion的数量 merge sort本身只不过是它的结构保证这个比较能traversal整个数组而已

这其实算不上妙用 什么算法课讲到divide and conquer， inversion几乎都是必讲的。

一通百通

求数组中逆序对也是merge sort好题，英文leetcode好像没有，国服有这道题。

593965536 发表于 2020-4-25 02:37
求数组中逆序对也是merge sort好题，英文leetcode好像没有，国服有这道题。

有的 leetcode 315就是逆序对 不过是让你求逆序对的数量

zhang3x7 发表于 2020-4-25 05:42
全都是数组中求inversion的变种 本质上是利用merge two sorted array的时候 两个array的指针指向较大那个元 ...

这样，怪以前算法课没学透

593965536 发表于 2020-4-25 02:37
求数组中逆序对也是merge sort好题，英文leetcode好像没有，国服有这道题。

315 就是逆序数的近亲。

https://zh.wikipedia.org/wiki/%E9%80%86%E5%BA%8F%E5%AF%B9

本质上这些都是 divide and conquer