返回介绍

lcci / 17.20.Continuous Median / README_EN

发布于 2024-06-17 01:04:42 字数 4530 浏览 0 评论 0 收藏 0

17.20. Continuous Median

中文文档

Description

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

  • void addNum(int num) - Add a integer number from the data stream to the data structure.
  • double findMedian() - Return the median of all elements so far.

Example:


addNum(1)

addNum(2)

findMedian() -> 1.5

addNum(3) 

findMedian() -> 2

Solutions

Solution 1

class MedianFinder:
  def __init__(self):
    """
    initialize your data structure here.
    """
    self.h1 = []
    self.h2 = []

  def addNum(self, num: int) -> None:
    heappush(self.h1, num)
    heappush(self.h2, -heappop(self.h1))
    if len(self.h2) - len(self.h1) > 1:
      heappush(self.h1, -heappop(self.h2))

  def findMedian(self) -> float:
    if len(self.h2) > len(self.h1):
      return -self.h2[0]
    return (self.h1[0] - self.h2[0]) / 2


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
class MedianFinder {
  private PriorityQueue<Integer> q1 = new PriorityQueue<>();
  private PriorityQueue<Integer> q2 = new PriorityQueue<>(Collections.reverseOrder());

  /** initialize your data structure here. */
  public MedianFinder() {
  }

  public void addNum(int num) {
    q1.offer(num);
    q2.offer(q1.poll());
    if (q2.size() - q1.size() > 1) {
      q1.offer(q2.poll());
    }
  }

  public double findMedian() {
    if (q2.size() > q1.size()) {
      return q2.peek();
    }
    return (q1.peek() + q2.peek()) * 1.0 / 2;
  }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
class MedianFinder {
public:
  /** initialize your data structure here. */
  MedianFinder() {
  }

  void addNum(int num) {
    q1.push(num);
    q2.push(q1.top());
    q1.pop();
    if (q2.size() - q1.size() > 1) {
      q1.push(q2.top());
      q2.pop();
    }
  }

  double findMedian() {
    if (q2.size() > q1.size()) {
      return q2.top();
    }
    return (double) (q1.top() + q2.top()) / 2;
  }

private:
  priority_queue<int, vector<int>, greater<int>> q1;
  priority_queue<int> q2;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */
type MedianFinder struct {
  q1 hp
  q2 hp
}

/** initialize your data structure here. */
func Constructor() MedianFinder {
  return MedianFinder{hp{}, hp{}}
}

func (this *MedianFinder) AddNum(num int) {
  heap.Push(&this.q1, num)
  heap.Push(&this.q2, -heap.Pop(&this.q1).(int))
  if this.q2.Len()-this.q1.Len() > 1 {
    heap.Push(&this.q1, -heap.Pop(&this.q2).(int))
  }
}

func (this *MedianFinder) FindMedian() float64 {
  if this.q2.Len() > this.q1.Len() {
    return -float64(this.q2.IntSlice[0])
  }
  return float64(this.q1.IntSlice[0]-this.q2.IntSlice[0]) / 2.0
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any)    { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
  a := h.IntSlice
  v := a[len(a)-1]
  h.IntSlice = a[:len(a)-1]
  return v
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文