LCR 160. 数据流中的中位数

1.题目

LCR 160. 数据流中的中位数

- `void addNum(int num)` - 从数据流中添加一个整数到数据结构中。- `double findMedian()` - 返回目前所有元素的中位数。

**输入：
**["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
**输出：**[null,null,null,1.50000,null,2.00000]

**输入：
**["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
**输出：**[null,null,2.00000,null,2.50000]

2.思路

addNum 数组是空直接插入，不是空就扩容然后往后移，而 findMedian 方法则根据数组元素数量的奇偶性计算中位数

3.代码

class MedianFinder {
public:// 成员变量 arr，用于存储数据流中的所有数字，使用 std::vector 容器来管理这些数字std::vector<int> arr;// 构造函数，在创建 MedianFinder 对象时调用，这里不做额外初始化操作，因为 arr 初始为空MedianFinder() {}// 向数据流中添加一个新数字的方法void addNum(int num) {// 检查 arr 是否为空if (arr.empty()) {// 如果 arr 为空，直接将新数字添加到 arr 中arr.push_back(num);} else {// 如果 arr 不为空，需要为新数字腾出位置，将 arr 的大小增加 1arr.resize(arr.size() + 1);// 定义一个整数变量 i，用于遍历数组int i;// 从数组倒数第二个元素开始向前遍历// 只要当前元素 arr[i] 大于要插入的数字 num，并且 i 不小于 0for (i = arr.size() - 2; i >= 0 && arr[i] > num; --i) {// 将当前元素向后移动一位，为新数字让出插入位置arr[i + 1] = arr[i];}// 当循环结束时，i + 1 位置就是新数字应该插入的位置arr[i + 1] = num;}}// 计算并返回当前数据流中位数的方法double findMedian() {// 这里注释掉了排序操作，因为在 addNum 方法中已经保证了数组有序// sort(arr.begin(), arr.end());// 检查 arr 中元素的数量是奇数还是偶数if (arr.size() % 2 == 1) {// 如果元素数量是奇数，中位数就是中间位置的元素// 将该元素转换为 double 类型后返回return arr[(arr.size()) / 2] * 1.0;} else {// 如果元素数量是偶数，中位数是中间两个元素的平均值// 先将中间两个元素转换为 double 类型，求和后除以 2 得到平均值并返回return (arr[(arr.size()) / 2] * 1.0 +arr[arr.size() / 2 - 1] * 1.0) /2.0;}}
};/*** 以下是调用示例的注释说明：* 这段注释给出了如何使用 MedianFinder 类的示例* 首先创建一个 MedianFinder 对象指针 obj，使用 new 关键字动态分配内存* 接着调用 obj 的 addNum 方法向数据流中添加一个数字 num* 最后调用 obj 的 findMedian 方法计算并获取当前数据流的中位数，存储在 param_2 中*/
// MedianFinder* obj = new MedianFinder();
// obj->addNum(num);
// double param_2 = obj->findMedian();