提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

golang刷leetcode：数据流中的中位数

2023-02-18 16:32:26 时间

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。

double findMedian() - 返回目前所有元素的中位数。

示例 1：

输入：

["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]

[[],[1],[2],[],[3],[]]

输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入：

["MedianFinder","addNum","findMedian","addNum","findMedian"]

[[],[2],[],[3],[]]

输出：[null,null,2.00000,null,2.50000]

限制：

最多会对 addNum、findMedian 进行 50000 次调用

解题思路

1，维护一个大根堆和一个小根堆

2，大根堆比小根堆长度大1或者相等

3，如果相等，先插入小根堆，弹出小根堆队首元素，插入大根堆

4，如果不等，先插入大根堆，弹出大根堆队首元素，插入小根堆

5，最后取队首元素的平均值或者长度更长的队首元素

代码实现 



type heap struct{
   data []int
   big bool
}

type MedianFinder struct {
   Little,Big *heap
}

func (h*heap)Hipfy(i int){
  l:=2*i+1
  r:=2*i+2
  max:=i
  if l<len(h.data) && h.Compare(l,max){
    max=l
  }

  if r<len(h.data) && h.Compare(r,max){
      max=r
  }
  if max!=i{
      h.data[max],h.data[i]=h.data[i],h.data[max]
      h.Hipfy(max)
  }
}

func (h*heap)Compare(i,j int)bool{
    if h.big{
        return h.data[i]>h.data[j]
    }
    return h.data[i]<h.data[j]
}

func (h*heap)Insert(i int){
    h.data=append(h.data,i)
    for i:=len(h.data)/2;i>=0;i--{
         h.Hipfy(i)
    }
}

func (h*heap)Pop()int{
    if len(h.data)<1{
        return -1
    }
    v:=h.data[0]
    h.data[0]=h.data[len(h.data)-1]
    h.data=h.data[:len(h.data)-1]
    h.Hipfy(0)
    return v
}


/** initialize your data structure here. */
func Constructor() MedianFinder {
   return MedianFinder{
       Little:&heap{},
       Big:&heap{big:true},
   }
}


func (this *MedianFinder) AddNum(num int)  {
     if len(this.Little.data)==len(this.Big.data){
        this.Little.Insert(num)
        v:=this.Little.Pop()
        this.Big.Insert(v)
        return 
     }
        this.Big.Insert(num)
        this.Little.Insert(this.Big.Pop())
}


func (this *MedianFinder) FindMedian() float64 {
   if len(this.Little.data)<len(this.Big.data){
       return float64(this.Big.data[0])
   }
   return float64(this.Big.data[0]+this.Little.data[0])/2.0
}


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

相关文章