leetcode295：数据流的中位数

题目链接

leetcode

题目描述

中位数是有序整数列表中的中间值。
如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// 295. 数据流的中位数

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

/*
    对于海量数据和流的数据，使用最大堆和最小堆来管理，把数据分为[小]|[大]两部分。
    最大堆保存前半部分的最大值，最小堆保存后半部分的最小值。
    保证左边和右边的个数之差不大于 1，且左边大于右边。
    
    时间复杂度：O(logn)
        添加操作的时间复杂度是 O(logn)，因为需要在堆中插入元素，并且在两个堆之间转移元素。
        查找操作的时间复杂度是 O(1)，因为只需要访问堆顶元素。
        对于每个元素的添加和查找操作，时间复杂度是 O(logn) 和 O(1)。
        对于整个数据流，添加了 n 个元素，总的时间复杂度是O(nlogn)。
    空间复杂度：O(n)
        最坏情况下，所有元素都存储在一个堆中。
*/
class MedianFinder_0 {
public:
    MedianFinder_0() {

    }
    
    void addNum(int num) {
        count ++;
        // 大根堆中的元素数量 >= 小根堆中的元素数量
        if (count % 2 == 1) { 
            minHeap.push(num);
            // 将大根堆的堆顶元素移动到小根堆中
            maxHeap.push(minHeap.top());
            minHeap.pop();
        } else {
            // 将小根堆的堆顶元素移动到大根堆中
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }
    
    double findMedian() {
        if (count % 2 == 1) {
            return maxHeap.top();
        } else {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        }
    }

private:
    int count = 0;
    priority_queue<int, vector<int>, less<int>> maxHeap;    // 大根堆（默认），存储较小的一半元素
    priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆，存储较大的一半元素
};

/*
    思路同上
*/
class MedianFinder {
public:
    MedianFinder() {

    }
    
    void addNum(int num) {
        // 大根堆中的元素数量 >= 小根堆中的元素数量
        if (maxHeap.size() == minHeap.size()) {
            minHeap.push(num);
            // 将大根堆的堆顶元素移动到小根堆中
            maxHeap.push(minHeap.top());
            minHeap.pop();
        } else {
            // 将小根堆的堆顶元素移动到大根堆中
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        } else {
            return maxHeap.top();
        }
    }

private:
    priority_queue<int, vector<int>, less<int>> maxHeap;    // 大根堆（默认），存储较小的一半元素
    priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆，存储较大的一半元素
};

int main() {
    vector<string> commands = {"MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"};
    vector<vector<int>> params = {{}, {1}, {2}, {}, {3}, {}};

    MedianFinder medianFinder;
    for (int i = 0; i < commands.size(); ++i) {
        if (commands[i] == "MedianFinder") {
            // 创建 MedianFinder 实例，已在 main 函数中创建
        } else if (commands[i] == "addNum") {
            medianFinder.addNum(params[i][0]);
        } else if (commands[i] == "findMedian") {
            cout << medianFinder.findMedian() << endl;
        }
    }

    return 0;
}

Golang 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package main

import (
	"container/heap"
	"fmt"
)

/*
   为了高效地维护数据流的中位数，可以使用两个优先队列（堆）：
       最大堆：存储较小的一半数据，堆顶是这一半的最大值。
       最小堆：存储较大的一半数据，堆顶是这一半的最小值。
   关键操作：
       插入操作：
           如果新元素小于或等于最大堆的堆顶，则插入到最大堆。
           否则，插入到最小堆。
           插入后，平衡两个堆的大小，确保最大堆的大小不超过最小堆的大小 + 1。
       获取中位数：
           如果两个堆的大小相等，中位数是两个堆顶的平均值。
           如果最大堆的大小比最小堆大 1，中位数是最大堆的堆顶。

   时间复杂度：O(logn)
       插入操作：每次插入操作的时间复杂度为 O(logn)，其中 n 是当前数据流的大小。
       获取中位数：时间复杂度为 O(1)，因为直接访问堆顶元素。
   空间复杂度：O(n)
       使用了两个堆来存储数据，空间复杂度为 O(n)，其中 n 是数据流的大小。
*/
// MedianFinder 数据结构
type MedianFinder struct {
    maxHeap *MaxHeap // 存储较小的一半数据
	minHeap *MinHeap // 存储较大的一半数据
}

// MaxHeap 最大堆实现
type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

// MinHeap 最小堆实现
type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func Constructor() MedianFinder {
    return MedianFinder{
		maxHeap: &MaxHeap{},
		minHeap: &MinHeap{},
	}
}

// AddNum 插入一个数字
func (this *MedianFinder) AddNum(num int)  {
    if this.maxHeap.Len() == 0 || num <= (*this.maxHeap)[0] {
		heap.Push(this.maxHeap, num)
	} else {
		heap.Push(this.minHeap, num)
	}

	// 平衡两个堆的大小
	if this.maxHeap.Len() > this.minHeap.Len() + 1 {
		heap.Push(this.minHeap, heap.Pop(this.maxHeap))
	} else if this.minHeap.Len() > this.maxHeap.Len() {
		heap.Push(this.maxHeap, heap.Pop(this.minHeap))
	}
}

// FindMedian 获取中位数
func (this *MedianFinder) FindMedian() float64 {
    if this.maxHeap.Len() == this.minHeap.Len() {
		return float64((*this.maxHeap)[0] + (*this.minHeap)[0]) / 2.0
	} else {
		return float64((*this.maxHeap)[0])
	}
}

func main() {
	// 测试用例
	testCases := []struct {
		actions []string
		values  [][]int
		expected []float64
	}{
		{
			actions: []string{"MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"},
			values:  [][]int{{}, {1}, {2}, {}, {3}, {}},
			expected: []float64{0, 0, 0, 1.5, 0, 2},
		},
		{
			actions: []string{"MedianFinder", "addNum", "findMedian"},
			values:  [][]int{{}, {1}, {}},
			expected: []float64{0, 0, 1},
		},
	}

	for i, tc := range testCases {
		mf := Constructor()
		outputs := []float64{0} // 初始化输出数组，包含第一个占位符 0

		for j := 1; j < len(tc.actions); j++ {
			switch tc.actions[j] {
			case "addNum":
				mf.AddNum(tc.values[j][0])
                outputs = append(outputs, 0) // 对于 addNum 操作，添加占位符 0
			case "findMedian":
				outputs = append(outputs, mf.FindMedian())
			}
		}

        fmt.Printf("Test Case %d, Input: actions = %v, values = %v\n", i+1, tc.actions, tc.values)
		if fmt.Sprint(outputs) == fmt.Sprint(tc.expected) {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, outputs)
		} else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, outputs, tc.expected)
		}
	}
}
#leetcode
leetcode295：数据流的中位数
https://lcf163.github.io/2024/05/06/leetcode295：数据流的中位数/
作者
乘风的小站
发布于
2024年5月6日
许可协议