题目链接
这道题两种方法，第一种一直维护两个heap，使他们的size差值小于等于1。每次插入的时候插入对应的heap，然后balance size。查询的时候，根据情况查询一个或者两个堆顶的元素。代码如下，时间复杂度O(n * log n)：
另外一种方法就是维护BST和mid指针，因为这里我们用duplicate的元素，所以我们要用multiset，注意multiset每次插入的时候，如果里面已经有duplicate，插入的位置就是duplicate对应的最末端。对于mid指针：
- 长度为奇数的时候，我们只想中间，这样查询的时候直接返回对应的值
- 长度为偶数的时候，只想中间较大的那一个，查询的时候和前面的一个算平均值
为了维护mid指针的正确性，每次插入的时候：
- 如果插入的比mid对应的值小，--mid;否则不变
- 假设原来长度为奇数
- 插入较小值，mid指向中间较小位置
- 插入较大值，mid指向中间较小位置
- 假设原来长度为偶数
- 插入较小值，mid指向中间
- 插入较大值，mid指向中间
- 所以之后我们还要对偶数长度进行调整，如果插入之后长度变成了偶数，++mid即可
时间复杂度O(n * log n)，代码如下：
No comments:
Post a Comment