【排序算法运用】剑指 Offer 41. 数据流中的中位数

共以下 5 个回答

• 小肸 永久会员 2023年9月17日 上午9:39

  class MedianFinder {
      static PriorityQueue<Integer> maxHeap;
      static PriorityQueue<Integer> minHeap;
      /** initialize your data structure here. */
      public MedianFinder() {
          //大根堆，存放小于中位数的数据
          maxHeap = new PriorityQueue<>((x, y) -> (y - x));
          //小根堆，存储大于中位数的数据
          minHeap = new PriorityQueue<>((x, y) -> (x - y));
      }
      //时间复杂度为O(logN)
      public void addNum(int num) {
          if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
              maxHeap.offer(num);
              if (maxHeap.size() > minHeap.size() + 1) {
                  minHeap.offer(maxHeap.poll());
              }
          } else {
              minHeap.offer(num);
              if (minHeap.size() > maxHeap.size()) {
                  maxHeap.offer(minHeap.poll());
              }
          }
  
      }
      //时间复杂度为O(1)
      public double findMedian() {
          if (maxHeap.size() > minHeap.size()) {
              return maxHeap.peek();
          }
          return (maxHeap.peek() + minHeap.peek()) / 2.0;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• sincere 普通 2023年9月11日 下午4:45

  • 思路：利用堆特性 保证left、right的堆顶元素为中间的两个：如果size()相等说明是偶数，需要往right加一个，不相等则往left加一个；返回时size()相等取两堆顶元素求平均值，不等取right堆顶
  • 复杂度：时间复杂度添加O(logN)查找O(1)，空间复杂度O(N)

  class MedianFinder {
      Queue<Integer> left, right;// 利用堆特性 保证left、right的堆顶元素为中间的两个
  
      /**
       * initialize your data structure here.
       */
      public MedianFinder() {
          left = new PriorityQueue<>((x, y) -> (y - x));// 大根堆 保存前半序列
          right = new PriorityQueue<>();// 小根堆 保存后半序列
      }
  
      // left保存N/2或(N-1)/2; right保存N/2或(N+1)/2
      // 如果size()相等说明是偶数，需要往right加一个，不相等则往left加一个
      public void addNum(int num) {
          if (left.size() == right.size()) {
              left.add(num);
              right.add(left.poll());
          } else {
              right.add(num);
              left.add(right.poll());
          }
      }
  
      // size()相等取两堆顶元素求平均值，不等取right堆顶
      public double findMedian() {
          if (left.size() == right.size()) {
              return (left.peek() + right.peek()) / 2.0;
          } else {
              return right.peek();
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年9月9日 上午10:31

  class MedianFinder {
      Queue<Integer> min, max;
      /** initialize your data structure here. */
      public MedianFinder() {
          min = new PriorityQueue<>(); // 小根堆，保存较大的数
          max = new PriorityQueue<>((x, y)-> (y - x)); // 大根堆，保存较小的数
      }
  
      public void addNum(int num) {
          //偶数,先去小根堆，拿出一个再去大根堆
          if (min.size() == max.size()) {
              min.add(num);
              max.add(min.poll());
          } else { //奇数,先去大根堆，拿出一个再去小根堆
              max.add(num);
              min.add(max.poll());
          }
      }
  
      public double findMedian() {
          //偶数
          if (min.size() == max.size()) {
              return (min.peek() + max.peek()) / 2.0;
          } else {// 奇数
              return max.peek() * 1.0;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 别扒拉我 普通 2023年9月9日 上午12:41

  插入排序

  class MedianFinder {
  
      private ArrayList<Integer> val;
      public MedianFinder() {
          val = new ArrayList<Integer>();
      }
  
      public void addNum(int num) {
          if(val.isEmpty()){
              val.add(num);
          }else{
              int i = 0;
              for(;i<val.size(); i++){
                  if(num <= val.get(i)){
                      break;
                  }
              }
              val.add(i,num);
          }
      }
  
      public double findMedian() {
          int len = val.size();
          if(len % 2 == 1){
              return (double)val.get(len/2);
          }else{
              double a = val.get(len/2);
              double b = val.get(len/2 - 1);
              return (a+b)/2;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 行动派小彩笔 普通 2023年9月7日 下午12:50

  //利用大小根堆的思想，将排序数组分成两半
  // 时间复杂度O()
  class MedianFinder {
  public:
      /** initialize your data structure here. */
      MedianFinder() {
  
      }
  
      void addNum(int num) {
          if(heap1.size()==heap2.size())
          {
              heap2.push(num);
              heap1.push(heap2.top());
              heap2.pop();
          }
          else
          {
              heap1.push(num);
              heap2.push(heap1.top());
              heap1.pop();
          }
      }
  
      double findMedian() {
          if(heap1.size()==heap2.size())
          {
              return (double)(heap2.top()+heap1.top())/2;
          }
          else return heap1.top();
      }
  private:
      priority_queue<int> heap1; //大根堆，保存前半部分
      priority_queue<int,vector<int>,greater<int>> heap2;//小根堆，保存后半部分
  };
  
  /**
   * Your MedianFinder object will be instantiated and called as such:
   * MedianFinder* obj = new MedianFinder();
   * obj->addNum(num);
   * double param_2 = obj->findMedian();
   */
  

  0 赞同 0 条回复

  登录以回复