请教一道hackrank题

快排最差就是O(n^2)

有可以避免最坏情况，保证O(n*log(n))的快排算法。https://en.wikipedia.org/wiki/Median_of_medians，但平均情况可能会比朴素的算法还要慢

O(lgN)解法： 很经典的一道面试题。 数据结构设计如下 max-heap -- median -- min-heap 来数根据这个数的和median的大小，把这个数放到或者max-heap里，或者min-heap里。然后调整两个heap里的数，使得两个heap是平衡的（size相等或者 左边size +1 = 右边size）。看一下数的总个数，如果总共有偶数个，median就是两个heap顶的数之和除以2， 如果总和是奇数个，那么median就是min-heap的堆顶。 时间复杂度分析： O(lgN)。每次添加只有siftup和siftdown操作。所以是lgN 类似题：leetcode 295 难度hard 这种数据结构的优势：可以处理超级超级长的数据，一台电脑的内存装不下的那种长度。 也可以处理源源不断的数据流，动态的实时返回中位数。 代码： 这里数据结构稍有不同，但是核心思想是一样的。只不过为了代码美观，使用了另外一种调整heap平衡的方式。核心思想是一样的。 public class MedianFinder { // max-heap PriorityQueue<Integer> left = new PriorityQueue<Integer>(Collections.reverseOrder()); // min-heap 和c++正好相反 PriorityQueue<Integer> right = new PriorityQueue<Integer>(); // Adds a number into the data structure. // 时刻满足left.size() == right.size() // 或者 left.size() == right.size() + 1 // 来数加左边，加完挤到右边一个数 // 挤过去以后 调整。 public void addNum(int num) { left.add(num); right.add(left.poll()); if (left.size() < right.size()) left.add(right.poll()); } // Returns the median of current data stream public double findMedian() { if (left.size() == right.size()) { return (left.peek() + right.peek()) * 0.5; } else { // left的堆顶元素是median return left.peek(); } } };

如果还需要增加删除操作呢？？ 遍历优先队列？ 假设值唯一 【 在 Sluggard 的大作中提到: 】 : O(lgN)解法： : 很经典的一道面试题。 : 数据结构设计如下 : ...................

之前好像是 CCF 还是啥有一个多堆的题，挺好的。 【 在 Sluggard 的大作中提到: 】 : O(lgN)解法： : 很经典的一道面试题。 : 数据结构设计如下 : ...................

请看题目补充 【 在 niabby 的大作中提到: 】 : 快排最差就是O(n^2)

感谢分析！所以最终快排的worst case时间复杂度是多少？ 【 在 Sluggard 的大作中提到: 】 : O(lgN)解法： : 很经典的一道面试题。 : 数据结构设计如下 : ...................

QAQ阅读能力不行 楼上维护两个堆找mid的做法可以并很经典，但这和快排有什么直接联系吗。。 如果要把那个当题目做的话，可能要根据那个array的奇怪性质选nlogn吧 说到底我是萌新。。不是很懂你司面试 【 在 silenceTYN 的大作中提到: 】 : 请看题目补充

快速划分的复杂度是O(n)，这里怎么着都不能比nlogn大啊。 我投logn一票。