題⽬描述

如何得到⼀個數據流中的中位數？如果從數據流中讀出奇數個數值，那麼中位數就是所有數值排序之後位於中間的數值。如果從數據流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。我們使⽤ Insert() ⽅法讀取數據流，使⽤ GetMedian() ⽅法獲取當前讀取數據的中位數。

思路及解答

排序列表法

維護一個列表，每次獲取中位數前進行排序

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MedianFinder1 {
    private List<Integer> data;
    
    public MedianFinder1() {
        data = new ArrayList<>();
    }
    
    // 插入數字到數據流
    public void Insert(Integer num) {
        data.add(num);
        // 每次插入後排序，保持列表有序
        Collections.sort(data);
    }
    
    // 獲取當前數據流的中位數
    public Double GetMedian() {
        int size = data.size();
        if (size == 0) return 0.0;
        
        if (size % 2 == 1) {
            // 奇數個元素，返回中間值
            return (double) data.get(size / 2);
        } else {
            // 偶數個元素，返回中間兩個數的平均值
            int mid = size / 2;
            return (data.get(mid - 1) + data.get(mid)) / 2.0;
        }
    }
}

• 插入操作：每次插入需要排序，時間複雜度O(n log n)
• 獲取中位數：直接通過索引訪問，時間複雜度O(1)
• 空間複雜度：O(n)，需要存儲所有數據

插入排序法

在方法一基礎上優化，在插入時就找到正確位置，避免每次都完整排序。同時利用二分查找找到插入位置，減少排序開銷

import java.util.ArrayList;
import java.util.List;

public class MedianFinder2 {
    private List<Integer> data;
    
    public MedianFinder2() {
        data = new ArrayList<>();
    }
    
    public void Insert(Integer num) {
        // 使用二分查找找到合適的插入位置
        int left = 0, right = data.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (data.get(mid) < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 在找到的位置插入元素
        data.add(left, num);
    }
    
    public Double GetMedian() {
        int size = data.size();
        if (size == 0) return 0.0;
        
        if (size % 2 == 1) {
            return (double) data.get(size / 2);
        } else {
            int mid = size / 2;
            return (data.get(mid - 1) + data.get(mid)) / 2.0;
        }
    }
}

• 插入操作：二分查找O(log n) + 插入操作O(n) = O(n)
• 獲取中位數：O(1)，通過索引直接訪問
• 優化效果：比方法一有明顯提升，特別適合部分有序的數據

雙堆法

是最高效的解法，利用大頂堆和小頂堆的特性來動態維護中位數，使用大頂堆存較小一半，小頂堆存較大一半

⽤⼀個數字來不斷統計數據流中的個數，並且創建⼀個最⼤堆，⼀個最⼩堆

• 如果插⼊的數字的個數是奇數的時候，讓最⼩堆⾥⾯的元素個數⽐最⼤堆的個數多 1 ，這樣⼀來中位數就是⼩頂堆的堆頂
• 如果插⼊的數字的個數是偶數的時候，兩個堆的元素保持⼀樣多，中位數就是兩個堆的堆頂的元素相加除以2 。

public class Solution {
	private int count = 0;
	private PriorityQueue<Integer> min = new PriorityQueue<Integer>();
	private PriorityQueue<Integer> max = new PriorityQueue<Integer>(new
	
	Comparator<Integer>() {
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}
	});
	
	public void Insert(Integer num) {
		count++;
		if (count % 2 == 1) {
			// 奇數的時候，需要最⼩堆的元素⽐最⼤堆的元素多⼀個。
			// 先放到最⼤堆⾥⾯，然後彈出最⼤的
			max.offer(num);
			// 把最⼤的放進最⼩堆
			min.offer(max.poll());
		} else {
			// 放進最⼩堆
			min.offer(num);
			// 把最⼩的放進最⼤堆
			max.offer(min.poll());
		}
	}
		
	public Double GetMedian() {
		if (count % 2 == 0) {
			return (min.peek() + max.peek()) / 2.0;
		} else {
			return (double) min.peek();
		}
	}
}

• 插入操作：堆的插入操作O(log n)，平衡操作O(log n)，總體O(log n)
• 獲取中位數：直接訪問堆頂元素，O(1)時間複雜度
• 空間複雜度：O(n)，需要存儲所有數據

為什麼這種方法有效？

• 大頂堆（maxHeap）：存儲數據流中較小的一半數字，堆頂是這一半中的最大值
• 小頂堆（minHeap）：存儲數據流中較大的一半數字，堆頂是這一半中的最小值
• 平衡維護：確保兩個堆的大小相差不超過1，這樣中位數就只與兩個堆頂有關