《算法进阶50讲》|《算法进阶50讲》中位数算法|树状数组|滑动窗口|堆|数

文章目录

- 前言
- 一、概念
- - 1、奇数
  - 2、偶数
- 二、数据流中位数
- - 1、问题描述
  - 2、算法思路
  - 3、时间复杂度
  - 4、源码分析
- 三、滑动窗口中位数
- - 1、问题描述
  - 2、算法思路
  - 3、时间复杂度
  - 4、源码分析
- 四、课后习题

前言一、概念 【《算法进阶50讲》|《算法进阶50讲》中位数】????什么是中位数？对于一个序列，中位数就是所有数值排序之后位于中间的数值。如果总共有偶数个数，那么中位数就是所有数排序之后中间两个数的平均值。
1、奇数
????如下图所示，这五个数排序以后，位于中的数是 4，所以中位数就是 4。

文章图片

2、偶数
????对于偶数的情况，排序以后，中间两个数是 4 和 7，所以中位数就是4 + 7 2 = 5.500000 \frac {4+7} {2} = 5.500000 24+7?=5.500000。

文章图片

二、数据流中位数 ????前置算法：《画解数据结构》画解二叉堆
1、问题描述

????设计一种容器，支持两种操作：
????void addNum(int num)- 从当前容器中添加一个整数。
????double findMedian()- 返回目前容器的中位数。
最多会对 addNum、findMedian进行1 0 5 10^5 105 次调用。

2、算法思路
???? ( 1 ) (1) (1) 准备两个堆，一个大顶堆，一个小顶堆。小顶堆中所有元素都是大于等于大顶堆的元素的。
???? ( 2 ) (2) (2) 如果能够保证两个堆元素的个数始终相差不超过 1，则可以在O ( 1 ) O(1) O(1) 的时间内快速得到整个序列的中位数；
???? ( 3 ) (3) (3) 如果总的元素个数是偶数，则为两个堆顶元素相加之和的平均数；如果总的元素个数是奇数，则为元素多的那个堆的堆顶，举个例子：

小顶堆元素	大顶堆元素
9 8 7	5 4 3 2
9 8 7	5 4 3
9 8 7 5	4 3 2

???? ( 4 ) (4) (4) 那么，进行元素插入呢？我们发现，小顶堆的元素是数组大的那一半，大顶堆的元素是数组小的那一半，所以我们可以根据它和小顶堆堆顶的元素大小，来选择插入哪个堆。假设插入的数为x x x，小顶堆堆顶的元素为t t t，则：
???????? ( 4.1 ) (4.1) (4.1)x ≥ t x \ge t x≥t，直接插入小顶堆；
???????? ( 4.2 ) (4.2) (4.2)x < t x < t x ????插入完毕，有可能导致两个堆的数量差值超过 1，于是需要进行调整操作；
???? ( 5 ) (5) (5) 如果小顶堆数量 < 大顶堆数量 - 1，则弹出大顶堆元素，放入小顶堆；反之，则将小顶堆元素弹出，放入大顶堆；
3、时间复杂度
???? ( 1 ) (1) (1) 插入：由于任何时候，在插入之前，两个堆的数据量差值不超过 1，所以插入以后必然不会超过 2，最多进行一次调整，一次调整的时间复杂度为O ( l o g 2 n ) O(log_2n) O(log2?n)。
???? ( 2 ) (2) (2) 查找：由于每次查找就是找两个堆的堆顶，所以时间复杂度为O ( 1 ) O(1) O(1)。
4、源码分析

class MedianFinder { priority_queue, greater<> > minHeap; priority_queue, less<> > maxHeap; public: MedianFinder() {// (1) while(!minHeap.empty()) minHeap.pop(); while(!maxHeap.empty()) maxHeap.pop(); }void balanceHeap() {// (2) int minSize = minHeap.size(); int maxSize = maxHeap.size(); if(minSize - maxSize < -1) { minHeap.push( maxHeap.top() ); maxHeap.pop(); }else if(minSize - maxSize > 1) { maxHeap.push( minHeap.top() ); minHeap.pop(); } }void addHeap(int num) {// (3) if(minHeap.empty()) { minHeap.push(num); return ; } if(num >= minHeap.top()) { minHeap.push(num); }else { maxHeap.push(num); } }void addNum(int num) {// (4) addHeap(num); balanceHeap(); }double findMedian() {// (5) int minSize = minHeap.size(); int maxSize = maxHeap.size(); if(minSize + maxSize == 0) { return 0; } if(minSize > maxSize) { return minHeap.top(); }else if(minSize < maxSize) { return maxHeap.top(); } return ( minHeap.top() + maxHeap.top() ) / 2.0; } };

?? ( 1 ) (1) (1) 初始化大顶堆和小顶堆；
?? ( 2 ) (2) (2) void balanceHeap()用于对两个堆进行平衡操作；
?? ( 3 ) (3) (3) addHeap(int num)用于根据数据的大小关系，决定插入大顶堆还是小顶堆；
?? ( 4 ) (4) (4) 实现插入API（插入 + 平衡）；
?? ( 5 ) (5) (5) 用O ( 1 ) O(1) O(1) 的时间复杂度计算中位数；
三、滑动窗口中位数 ????前置算法：
???????? ( 1 ) (1) (1) 哈希表
???????? ( 2 ) (2) (2) 离散化
???????? ( 3 ) (3) (3) 二分枚举
???????? ( 4 ) (4) (4) 前缀和
???????? ( 5 ) (5) (5) 树状数组
1、问题描述

????给你一个数组 nums，有一个长度为k k k 的窗口从最左端滑动到最右端。窗口中有k k k 个数，每次窗口向右移动 1 位。找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

2、算法思路
???? ( 1 ) (1) (1) 我们先把前k k k 个数丢到一个容器中；
???? ( 2 ) (2) (2) 如果k k k 为奇数，则就是求这个容器的第k + 1 2 \frac {k+1}{2} 2k+1? 大的数；如果k k k 为偶数，则就是求这个容器的第k 2 \frac {k}{2} 2k? 大的数和k 2 + 1 \frac {k}{2}+1 2k?+1 大的数的平均值；
???? ( 3 ) (3) (3) 然后，窗口滑动一格，其实就是从容器中删除一个元素、加入另一个元素。
???? ( 4 ) (4) (4) 于是，我们需要提供一种容器，能够支持以下三种操作：
???????? ( 4.1 ) (4.1) (4.1) 插入；
???????? ( 4.2 ) (4.2) (4.2) 删除；
???????? ( 4.3 ) (4.3) (4.3) 查询k k k 大数；
???? ( 5 ) (5) (5) 这个k k k 大数的容器，我们可以采用树状数组来实现，利用二分枚举答案 + 树状数组的求和通过O ( l o g 2 2 n ) O(log_2^2n) O(log22?n) 的时间复杂度快速找到第k k k 大的数。
3、时间复杂度
???? ( 1 ) (1) (1) 插入： O ( l o g 2 n ) O(log_2n) O(log2?n)
???? ( 2 ) (2) (2) 删除： O ( l o g 2 n ) O(log_2n) O(log2?n)
???? ( 3 ) (3) (3) 求k k k 大数： O ( l o g 2 2 n ) O(log_2^2n) O(log22?n)
4、源码分析

class Solution { vector bin; unordered_map value2Index; int c[300000]; void discritizen(vector& nums) {// (1) int i; bin.clear(); for(i = 0; i < nums.size(); ++i) { bin.push_back(nums[i]); } sort(bin.begin(), bin.end()); // (1.1) bin.erase( unique(bin.begin(), bin.end()), bin.end() ); // (1.2)value2Index.clear(); for(i = 0; i < bin.size(); ++i) {// (1.3) value2Index[ bin[i] ] = i + 1; } }// 根据 x 的值，返回需要操作数组对应下标 int getIndex(int x) {// (2) return value2Index[x]; }int getValue(int index) {// (3) return bin[ index-1 ]; }int getMaxIndex() { return bin.size(); }int lowbit(int x) { return x & -x; }void add(int x, int n, int v) {// (4) while(x <= n) { c[x] += v; x += lowbit(x); } }int sum(int x) {// (5) int s = 0; while(x) { s += c[x]; x -= lowbit(x); } return s; }int getkth(int K) {// (6) int l = 1, r = getMaxIndex(); int ans = -1; while(l <= r) { int mid = (l + r) >> 1; if(sum(mid) >= K) { ans = mid; r = mid - 1; }else { l = mid + 1; } } return ans; }double getk(int k) {// (7) if(k & 1) { return getValue( getkth( (k+1)/2 ) ); } return ( (double)getValue( getkth( k/2 ) ) + getValue( getkth( k/2 + 1 ) ) ) / 2.0; }public: vector medianSlidingWindow(vector& nums, int k) { int i; vector ret; discritizen(nums); for(i = 0; i < nums.size(); ++i) { if(i >= k) add(getIndex(nums[i-k]) , getMaxIndex(), -1); // -1 表示删除这个数 add(getIndex(nums[i]) , getMaxIndex(), 1); // +1 表示插入这个数 // 求解 if(i >= k - 1) { ret.push_back(getk(k) ); } } return ret; } };

???? ( 1 ) (1) (1) void discritizen(vector& nums)就是将数组里面的负数、以及非常大的数映射到一个树状数组能够接受的范围内，这就是离散化（例如将[ ? 1 , 0 , 1 ] [-1, 0, 1] [?1,0,1] 映射到[ 1 , 2 , 3 ] [1, 2, 3] [1,2,3]）；
???????? ( 1.1 ) (1.1) (1.1) 离散化三部曲：第一步 - 排序；
???????? ( 1.2 ) (1.2) (1.2) 离散化三部曲：第二步 - 去重；
???????? ( 1.2 ) (1.2) (1.2) 离散化三部曲：第三步 - 反向映射；
???? ( 2 ) (2) (2) int getIndex(int x)通过数值，快速获取它离散化后的值；
???? ( 3 ) (3) (3) int getValue(int index)通过离散化后的值找回原来的值；
???? ( 4 ) (4) (4) void add(int x, int n, int v)是树状数组的插入操作，可以理解成在数组[ 1 , n ] [1, n] [1,n] 的x x x 位置上，加上一个值v v v；
???? ( 5 ) (5) (5) int sum(int x)是树状数组的求和操作，计算数组[ 1 , x ] [1, x] [1,x] 上的所有值的和；
???? ( 6 ) (6) (6) int getkth(int K)求的是容器中第K大的那个下标，假设树状数组中的元素，展平以后如下：

下标	1	2	3	4
值	4	5	0	0
和	4	9	9	9

那么我们要求的就是第 5 大的数，也就是求前缀和大于等于 5 的最小下标，前缀和必然满足单调不降，于是，可以二分枚举这个下标求解即可。
???? ( 7 ) (7) (7) 如果k k k 为奇数，则就是求这个容器的第k + 1 2 \frac {k+1}{2} 2k+1? 大的数；如果k k k 为偶数，则就是求这个容器的第k 2 \frac {k}{2} 2k? 大的数和k 2 + 1 \frac {k}{2}+1 2k?+1 大的数的平均值；注意，求出来的是映射后的下标，需要将原值返回。
四、课后习题

序号	题目链接	难度
1	LeetCode 295. 数据流的中位数	★★★☆☆
2	面试题 17.20. 连续中值	★★★☆☆
3	剑指 Offer 41. 数据流中的中位数	★★★☆☆
4	LeetCode 480. 滑动窗口中位数	★★★★☆