给定一个数据流 arr[]，其中的整数是按顺序读取的。我们需要确定在每读入一个新的整数后，目前遇到的所有元素的中位数。
根据数据集的大小，中位数的情况分为两种：
- 如果数据集包含奇数个元素，则中间的那个元素将被视为中位数。
- 如果数据集包含偶数个元素，则没有单一的中间值，中位数将是两个中间值的算术平均值。
示例：
> 输入： arr[] = [5, 15, 1, 3, 2, 8]
> 输出： [5.00, 10.00, 5.00, 4.00, 3.00, 4.00]
> 解释：
> 读入数据流的第 1 个元素后 – 5 -> 中位数 = 5
> 读入数据流的第 2 个元素后 – 5, 15 -> 中位数 = (5+15)/2 = 10
> 读入数据流的第 3 个元素后 – 5, 15, 1 -> 中位数 = 5
> 读入数据流的第 4 个元素后 – 5, 15, 1, 3 -> 中位数 = (3+5)/2 = 4
> 读入数据流的第 5 个元素后 – 5, 15, 1, 3, 2 -> 中位数 = 3
> 读入数据流的第 6 个元素后 – 5, 15, 1, 3, 2, 8 -> 中位数 = (3+5)/2 = 4
>
> 输入： arr[] = [2, 2, 2, 2]
> 输出： [2.00, 2.00, 2.00, 2.00]
> 解释：
> 读入数据流的第 1 个元素后 – 2 -> 中位数 = 2
> 读入数据流的第 2 个元素后 – 2, 2 -> 中位数 = (2+2)/2 = 2
> 读入数据流的第 3 个元素后 – 2, 2, 2 -> 中位数 = 2
> 读入数据流的第 4 个元素后 – 2, 2, 2, 2 -> 中位数 = (2+2)/2 = 2
目录
- [朴素方法] 使用插入排序
- [推荐方法] 使用堆
[朴素方法] 使用插入排序
> 如果我们知道直到当前索引为止元素的排序顺序，我们就可以很容易地通过中间元素找到数据流的中位数。为了保持排序顺序，我们在每一步都使用插入排序的方法，将新元素插入到其正确的位置。一旦列表排序到当前索引，我们就利用目前的元素总数来找到中位数：
>
> – 如果计数是偶数，取两个中间元素的算术平均值。
> – 如果计数是奇数，取中间的那个元素作为中位数。
为什么要用插入排序？
插入排序允许我们维护一个动态排序的数组。在每一步中，我们只需将当前元素插入到已排序部分的正确位置，这使得寻找中位数变得非常容易。
C++
CODEBLOCK_d6d07e82
Java
import java.util.ArrayList;
import java.util.Arrays;
class GfG {
static ArrayList getMedian(int[] arr) {
ArrayList res = new ArrayList();
res.add((double) arr[0]);
for (int i = 1; i < arr.length; i++) {
int j = i – 1;
int num = arr[i];
// 向右移动元素以便为将当前元素
// 插入到正确位置腾出空间
while (j >= 0 && arr[j] > num) {
arr[j + 1] = arr[j];
j–;
}
arr[j + 1] = num;
int len = i + 1;
double median;
// 如果从流中读取的整数个数为奇数
// 则排序后的中间元素即为中位数
// 否则为中间两个元素的平均值
if (len % 2 != 0) {
median = arr[len / 2];
} else {
median = (arr[(len / 2) – 1] + arr[len / 2]) / 2.0;
}
res.add(median);
}
return res;
}
public static void main(String[] args) {
int[] arr = {5, 15, 1, 3, 2, 8};
ArrayList res = getMedian(arr);