这道题有两种做法。首先我们知道merge sort可以解counting inversions类的题目，具体做法请参考上面的链接。我们可以用类似的做法来解这一题，上面的题是求解总的inversions，但是这道题需要求解每个元素和其后面的元素形成的inversions，显然我们需要在sort的时候追踪当前数在原来array num中对应的index是多少。我们要实现这一点，可以间接地sort array，也就是说，我们新建一个index array，存num中每个元素对于的下标，那么index起始的时候就应该是{1,2,3,4,5...}的样子，我们sort index array，而不是原来的num。例如num = {5,1,4,2}, index = num{0,1,2,3}，我们只sort index array， num array是用来比较的时候用index里的下标来access真正的值。那么sort之后，num不变，index = {1,3,2,0}，转换成num对应的数的话就是{1,2,4,5}。这样当我们counting当前数对应的reverse paris的时候，我们可以直接知道其在num中对应的原坐标是多少。时间复杂度就是merge sort的复杂度O(n * log n)，代码如下：
另外一种方法我们可以用BST，因为在这边文章中讲过，node中多存一个size的节点，就可以在log n的时间里查询有多少个小于它的节点，我们只需要从右向左，一遍构建BST一遍查询就可以。时间复杂度也是O(n * log n)，代码如下：
除了以上两个方法之外，这同时也是一道range query的题目。因为对于每一个数num，我们想要知道其右边有多少个数小于它，就相当于对所有在其右边的数进行一个[minVal, num)的range query来统计出现了多少个。而我们可以用Binary Indexed Tree或者Segment Tree实现这些区间查询，我们要存的就是当前节点表示的范围里面有多少个数已经出现了(重复的当然也要计算)。具体的原理可以参考上面给出的文章链接，这里因为数字的范围很大，我们将其压缩到[0, N)的区间即可，N为输入数组的长度。值得一提的一点，Reverse Pairs这道很相似的题我们没有办法进行输入数据的压缩，因为压缩过后很有可能对于一些数，原先满足题目中给出关系的会不再满足，也就是说原先是两倍的关系，压缩之后可能就不是了，所以我们没法用BIT或者Segment Tree实现。BIT和Segment Tree在区间查询的时候都可以达到O(log N)的时间复杂度，所以总的时间复杂度也是O(log N)，空间复杂度O(N)。代码如下：
Segment Tree:
BIT:
No comments:
Post a Comment