动画设计工资_全国疫情最新消息今天新增多少例_班级优化大师_短视频seo询盘获客系统

---

• 原题链接：295. 数据流的中位数

---

1- 思路

题目识别

• 识别1 ：实现一个数据结构，求中位数

堆实现

思路

• 利用优先队列，小根堆放较小的元素。
• 大根堆放较大的元素。
• 例如 1 2 3 4 5 6 ，其中大根堆放的元素是 1 2 3，小根堆放的元素是 4 5 6。中位数就是 (3+4)/2

实现

• ① 当是偶数
  • 先入小根堆，之后大根堆添加小根堆堆顶元素。
• ② 当是奇数
  • 先入大根堆，之后小根堆添加大根堆堆顶元素。

---

2- 实现

⭐4. 寻找两个正序数组的中位数——题解思路

class MedianFinder {Queue<Integer> min;Queue<Integer> max;public MedianFinder() {min = new PriorityQueue<>((x,y) -> (y-x));max = new PriorityQueue<>();}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;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

---

3- ACM 实现

package Daily_LC.Month9_Week3.Day157;import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;/*** findMid** @author alcohol* @Description* @since 2024-09-17 12:38*/
public class findMid {static Queue<Integer> min;static Queue<Integer> max;public findMid(){min = new PriorityQueue<>((x,y) -> (y-x));max = new PriorityQueue<>();}public static void add(int num){if(min.size() == max.size()){min.add(num);max.add(min.poll());}else{max.add(num);min.add(max.poll());}}public static double getMid(){if(min.size() == max.size()){return (min.peek()+max.peek())*0.5;}else{return max.peek()*1.0;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine(); // 消耗换行符findMid fm = new findMid();for(int i = 0 ; i < n ; i ++){String ope = sc.nextLine();if(ope.equals("addNum")){System.out.println("输入添加的数");int num = sc.nextInt();sc.nextLine(); // 消耗换行符fm.add(num);}else if(ope.equals("findMedian")){System.out.println(fm.getMid());}}}
}