Java solution with two priority queues(30ms)


  • 0
    G

    The trick is if we use a max heap to keep the low half data, and a min heap to keep the high half data, then we can get the current median easily.

      public void addNum(int num) {
        // add element
        if (lowHalf.isEmpty() || lowHalf.peek() >= num) {
          lowHalf.offer(num);
        } else {
          highHalf.offer(num);
        }
    
        // keep balance
        if (lowHalf.size() - highHalf.size() > 1) {
          highHalf.offer(lowHalf.poll());
        }
        if (highHalf.size() - lowHalf.size() > 1) {
          lowHalf.offer(highHalf.poll());
        }
      }
    
      // Returns the median of current data stream
      public double findMedian() {
        double curMed = 0;
        if (lowHalf.isEmpty() || highHalf.size() > lowHalf.size()) {
          curMed = highHalf.peek();
        } else if (highHalf.isEmpty() || lowHalf.size() > highHalf.size()) {
          curMed = lowHalf.peek();
        } else {
          curMed = (lowHalf.peek() + highHalf.peek()) / 2.0; // 偶数个元素
        }
    
        return curMed;
      }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.