leetcode.295

C 链表设计

刷题

发布日期: 2022-03-24

LeetCode 295.数据流的中位数

1 题目描述

题目链接：295.数据流的中位数
题目链接：剑指 Offer 41. 数据流中的中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

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

示例 1:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？

如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

2 思路

用一个双向链表记录数据，用一个mid指针指向当前链表中的中间结点，并维护由Head指向next方向上呈递增的关系，即维护一个递增的双向链表，并在加入新结点时对mid指针进行维护。数据结构如下

typedef struct MyListNode {
    int val;                    //记录数据流的数据
    struct MyListNode *prev;    
    struct MyListNode *next;
}ListNode;

typedef struct {
    int cnt;                    //数据流中的数据数
    ListNode *head;             //虚拟头结点，方便插入
    ListNode *mid;              //中间结点
} MedianFinder;

mid指针的维护：首先，让mid指向链表头，当结点个数为奇数时mid指针向后移动一位，即：

if(obj->cnt%2){
    obj->mid = obj->mid->next;
}

需要注意的是，当当前插入的结点的值小于等于mid->val时，插入结点的位置是在mid的左侧，会导致mid自动地后移一位，存在一种最差的情况：后插入的结点全部在第一个插入结点的左侧，因而mid就相当于跑到链表中的最后一个位置，因此，我们需要对num < mid->val这种情况进行以下处理：

if(num <= obj->mid->val){
    obj->mid = obj->mid->prev;
}

即当num < mid->val时，将mid向前移动一步，然后再判断是否需要往后移一步。整体代码如下：

typedef struct MyListNode {
    int val;
    struct MyListNode *prev;
    struct MyListNode *next;
}ListNode;

typedef struct {
    int cnt;            //当前链表中的数据量
    ListNode *head;
    ListNode *mid;
} MedianFinder;

/** initialize your data structure here. */

MedianFinder* medianFinderCreate() {
    MedianFinder *ret = (MedianFinder *)malloc(sizeof(MedianFinder));
    ret->cnt = 0;
    ret->head = (ListNode *)malloc(sizeof(ListNode));
    ret->head->val = INT_MIN;
    ret->head->prev = NULL;
    ret->head->next = NULL;
    ret->mid = ret->head;
    return ret;
}

void medianFinderAddNum(MedianFinder* obj, int num) {
    obj->cnt += 1;                  //数据量加1
    ListNode *cur = obj->head; 
    while(cur && cur->next && cur->next->val < num){
        cur = cur->next;            //查询结点插入位置
    }
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->val = num;
    if(cur->next){                  //判断插入位置是否在最后
        cur->next->prev = node; 
    }
    node->next = cur->next;
    node->prev = cur;
    cur->next = node;
    if(num <= obj->mid->val){       //处理插入结点在mid左侧的情况
        obj->mid = obj->mid->prev;
    }
    if(obj->cnt%2){                 //奇数时中位数指针后移一位
        obj->mid = obj->mid->next;
    }
}

double medianFinderFindMedian(MedianFinder* obj) {
    //判断obj->cnt是否为0是避免出现链表为空时调用了medianFinderFree()
    if(obj->cnt && obj->cnt % 2){   //奇数时
        return (double)obj->mid->val;
    }else if(obj->cnt){             //偶数时
        return (double)(obj->mid->val + obj->mid->next->val)/2;
    }
    return 0;
}

void medianFinderFree(MedianFinder* obj) {
    ListNode *tmp = obj->head, *next = tmp->next;
    while(next){
        free(tmp);
        tmp = next;
        next = tmp->next;
    }
    free(tmp);
    free(obj);
}

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

* double param_2 = medianFinderFindMedian(obj);

* medianFinderFree(obj);
*/