532. Reverse Pairs

MergeSort 的最牛的题目了私以为。但是起始干货很少。

mergesort和merge方法都要返回sum了,即reverse pair的个数。

reverse pair的计算在真正merge的时候发生,其他的部分都是在传球接力。唯一要记得的一个地方是,发现后一半比前一半小的时候,此时累计的pair数量是mid-left+1。 BTW,循环是while(left<=mid && right<=end)

还有一个注意的地方是merge需要用一个temp数组来暂时存放merge的数组,但是一定不要忘记了最后还要把temp再还给原数组。这个包括left或者right没有比较完的剩余部分x2和最后temp里全部还给数组两个操作。如果不做这一步,数组是没有进行完mergesort的,结果肯定是不对的。

Show your support

Clapping shows how much you appreciated DeReK’s story.