扫码订阅《 》或入驻星球,即可阅读文章!

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • Go下载

    • 视频资源
    • 文档资源
Go求职
  • 求职服务

    • 内推互助
    • 求职助力
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
Go友会
  • 城市
  • 校园
推广返利 🤑
实验区
  • Go周边
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • Go下载

    • 视频资源
    • 文档资源
Go求职
  • 求职服务

    • 内推互助
    • 求职助力
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
Go友会
  • 城市
  • 校园
推广返利 🤑
实验区
  • Go周边
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • 面试宝典系列

    • 剑指 Offer 题解
  • 数组与矩阵

  • 栈队列堆

    • 9. 用两个栈实现队列
    • 30. 包含 min 函数的栈
    • 31. 栈的压入、弹出序列
    • 40. 最小的 K 个数
    • 41.1 数据流中的中位数
    • 59. 滑动窗口的最大值
  • 双指针

  • 链表

  • 树

  • 贪心思想

  • 二分查找

  • 分治

  • 搜索

  • 排序

  • 动态规划

  • 数学

  • 位运算

  • 其他

扫码订阅《 》或入驻星球,即可阅读文章!

41.1 数据流中的中位数


GOLANG ROADMAP

# 题目链接

牛客网 (opens new window)

力扣 (opens new window)

# 题目描述

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

# 解题思路

image.png

type MedianFinder struct {
	minHeap []int
	maxHeap []int
	length  int
}

/** initialize your data structure here. */
func Constructor() MedianFinder {
	return MedianFinder{
		minHeap: []int{},
		maxHeap: []int{},
		length:  0, // 记录存入元素的个数
	}
}

// 上浮 用于堆尾插入元素 调整堆  cmp函数是为了控制是大顶堆还是小顶堆
func upAdjust(arr []int, cmp func(x, y int) bool) {
	if len(arr) == 0 {
		return
	}
	length := len(arr)
	child := length - 1
	parent := (child - 1) / 2
	newValue := arr[child]
	for child > 0 {
		if cmp(newValue, arr[parent]) { // 满足条件上浮  小顶堆 就是 newValue 小于  交换 当前 大顶堆就是大于当前
			arr[child] = arr[parent]
			child = parent
			parent = (child - 1) / 2
		} else {
			break
		}
	}
	arr[child] = newValue
}

// 下沉 用于删除堆顶元素后 调整堆
func downAdjust(arr []int, i int, cmp func(x, y int) bool) {
	if len(arr) == 0 {
		return
	}
	parent := i
	child := 2*parent + 1
	rootValue := arr[parent]
	for child < len(arr) {
		if child+1 < len(arr) && cmp(arr[child+1], arr[child]) { // 小顶堆 就是寻找小的 child 用于以后比较 大顶堆就是寻找大的
			child++
		}
		if cmp(arr[child], rootValue) { // 满足条件下沉  小顶堆 就是 rootValue 大于当前 交换   大顶堆就是 小于当前
			arr[parent] = arr[child]
			parent = child
			child = parent*2 + 1
		} else {
			break
		}
	}
	arr[parent] = rootValue
}
// 维护小顶堆
func cmpMin(x, y int) bool {
	return x < y
}
// 维护大顶堆
func cmpMax(x, y int) bool {
	return x > y
}

// 添加数
func (this *MedianFinder) AddNum(num int) {
	this.length++
	if this.length%2 == 0 {
		//fmt.Println("min:", this.minHeap)
		// 存入小顶堆 并调整
		this.minHeap = append(this.minHeap, num)
		upAdjust(this.minHeap, cmpMin)
		// 弹出小顶堆栈顶存入大顶堆
		this.maxHeap = append(this.maxHeap, this.minHeap[0])
		Pop(&this.minHeap)
		// 调整弹出元素后的小顶堆 和 新加元素的大顶堆
		downAdjust(this.minHeap, 0, cmpMin)
		upAdjust(this.maxHeap, cmpMax)
	} else if this.length%2 == 1 { // 保证堆平衡 维护大小顶堆长度 相差不大于1
		//fmt.Println("max:", this.maxHeap)
		// 存入大顶堆 并调整
		this.maxHeap = append(this.maxHeap, num)
		upAdjust(this.maxHeap, cmpMax)
		// 弹出大顶堆堆顶 并存入小顶堆
		this.minHeap = append(this.minHeap, this.maxHeap[0])
		Pop(&this.maxHeap)
		//fmt.Println("max:", this.maxHeap)
		// 调整弹出元素后的大顶堆 和 新加元素的小顶堆
		downAdjust(this.maxHeap, 0, cmpMax)
		upAdjust(this.minHeap, cmpMin)
		//fmt.Println("min:", this.minHeap)
	}
	return
}

// 弹出堆顶元素 并将堆尾元素放入堆顶  调整堆的长度
func Pop(arr *[]int) { // 这块坑我好久  对于切片的更改  只更改值可以使用值形式 但是更改长度 需要使用指针  很重要
	length := len(*arr)
	if length == 1 { // 若堆只有一个元素 那么无法交换 返回空数组
		*arr = (*arr)[:length-1]
	}
	if length > 1 {
		(*arr)[0] = (*arr)[length-1]
		*arr = (*arr)[:length-1]
	}
}

// 计算中位数
func (this *MedianFinder) FindMedian() float64 {
	if this.length%2 == 1 {
		return float64(this.minHeap[0])
	}
	if this.length%2 == 0 {
		return (float64(this.maxHeap[0]) + float64(this.minHeap[0])) / 2
	}
	return 0
}


/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */
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
  • 题目链接
  • 题目描述
  • 解题思路