跳转至

295. 数据流的中位数

最后更新：2024-05-10-22

链接：https://leetcode.cn/problems/find-median-from-data-stream/description/

题目描述

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

  • 例如 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 以内的答案将被接受。

题目示例

输入： ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]

[[], [1], [2], [], [3], []]

输出： [null, null, null, 1.5, null, 2.0]

解释：

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示：

  • \(-10^5 <= num <= 10^5\)
  • 在调用 findMedian 之前，数据结构中至少有一个元素
  • 最多 \(5 * 10^4\) 次调用 addNum 和 findMedian

思路

题目要求获取中位数，那么必然涉及到排序，但是排序的话，我们不可能每次计算中位数的时候，都去排序，这样太耗时，最好的办法，就是我们维护一个有序的数组。

就是大多数人说的插入排序。

  • 插入的时候，先找到要插入的位置，我这里是按照降序去处理的，找插入的位置时，可以使用二分法；
  • 找到位置后，pos以及之后的数据都往后移动一位，移动的长度是size-pos；
  • 在pos位置插入新值num，然后size++；
  • 计算中位数按照正常的计算方法计算就行。

主要的优化点就是找pos以及维护好这个有序的数组。

查找如果用其他的算法，可能会耗时很多，二分法算是一个比较快的查找算法了。

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
#define MAX_NUMS_SIZE 19000

typedef struct {
    int nums[MAX_NUMS_SIZE + 1];
    int numsSize;
} MedianFinder;

/** initialize your data structure here. */

MedianFinder* medianFinderCreate()
{
    MedianFinder *obj = (MedianFinder*)malloc(sizeof(MedianFinder));
    if (obj == NULL) {
        return NULL;
    }

    obj->numsSize = 0;
    memset(obj->nums, 0, sizeof(obj->nums));

    return obj;
}

void printfMedianFinder(MedianFinder* obj)
{
    for (int i = 0; i < obj->numsSize; i++) {
        printf("%d ", obj->nums[i]);
    }
    printf("\n");
}

int medianFindInsertPosition(MedianFinder* obj, int num)
{
    int left = 0;
    int right = obj->numsSize - 1;

    while (left <= right) {
        int m = left + (right - left) / 2;
        if (obj->nums[m] == num) { // 找到了
            return m;
        } else if (obj->nums[m] > num) {
            left = m + 1;
        } else {
            right = m - 1;
        }
    }

    return left;
}

void medianFinderAddNum(MedianFinder* obj, int num)
{
    if ((obj == NULL) || (obj->numsSize >= MAX_NUMS_SIZE)) {
        return;
    }

    // 找到要插入的位置
    int pos = medianFindInsertPosition(obj, num);

    // pos之后的内容后移一个位置，移动obj->numsSize - pos个数
    memmove(&obj->nums[pos + 1], &obj->nums[pos], sizeof(int) * (obj->numsSize - pos));
    // 插入pos
    obj->nums[pos] = num;
    obj->numsSize++;

    // printfMedianFinder(obj);
}

double medianFinderFindMedian(MedianFinder* obj)
{
    int mid;
    double result = 0.0;

    if ((obj == NULL) || (obj->numsSize == 0)) {
        return 0.0;
    }

    mid = obj->numsSize / 2;
    // printf("mid %d, obj->numsSize %d, obj->nums[mid] %d\n", mid, obj->numsSize, obj->nums[mid]);
    if ((obj->numsSize % 2) == 0) {
        result = obj->nums[mid - 1] / 2.0 + obj->nums[mid] / 2.0;
    } else {
        result = (double)obj->nums[mid];
    }

    return result;
}

void medianFinderFree(MedianFinder* obj)
{
    free(obj);
    obj = NULL;
}

/**
* Your MedianFinder struct will be instantiated and called as such:
* MedianFinder* obj = medianFinderCreate();
* medianFinderAddNum(obj, num);

* double param_2 = medianFinderFindMedian(obj);

* medianFinderFree(obj);
*/
Go
1