[leetcode 295]Find Median from Data Stream 原创解法

发表于 更新于

题目概述

原题链接

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: 
 `[2,3,4]` , the median is 3

 `[2,3]`, the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

- void addNum(int num) - Add a integer number from the data stream to the data structure. 
- double findMedian() - Return the median of all elements so far.   
For example:

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

第一想到的解法

找到一串数字的中位数，那么首先要对数字进行排列。否则怎么知道哪个 数字是处于中间的呢。快排是不行的，因为快排是一个离线算法。必须要 读进所有的数字。总不能每增加一个数做一次快排吧。 插入排序是一种在线算法，每增加一个数字遍历一遍就好。 那就实现一下吧。以下是实现的解法。但是超时了。

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
#python3
class MedianFinder(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.q = []

    def addNum(self, num):
        """
        :type num: int
        :rtype: void
        """
        if not self.q:
            self.q.append(num)
        else:
            i = len(self.q) - 1
            while i >= 0:
                if self.q[i] > num:
                    i -= 1
                else:
                    break
            self.q.insert(i + 1, num)

    def findMedian(self):
        """
        :rtype: float
        """
        if self.q:
            n = len(self.q)
            r = n % 2
            if r == 0:
                mid = n // 2
                return (self.q[mid - 1] + self.q[mid]) / 2.0
            else:
                mid = (n - 1) // 2
                return self.q[mid]

使用链表

这个方法再插入一个数字的时间复杂度也是O(n)，所以如果我们不使用 python的list而是使用一个自己创建的链表，那么插入的时间复杂度 是O(1)至少应该快一些。嗯，重新实现一遍。以下是实现的代码，但是 还是超时了。而且速度和前一种相当。说明python内置的list效率是相当 高的。

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
# python3
class Linker(object):
    def __init__(self, v):
        self.pre = None
        self.v = v
        self.next = None


class MedianFinder1(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.median = None
        self.end = None
        self.odd = None

    def addNum(self, num):
        """
        :type num: int
        :rtype: void
        """
        if not self.end:
            self.end = Linker(num)
            self.mid = self.end
            self.mid_next = None
            self.odd = True  # 是否增加了计数个
        else:
            self.odd = not self.odd
            tmp = self.end
            tmp_next = None
            while tmp and tmp.v > num: 
                tmp_next = tmp
                tmp = tmp.pre

            linker = Linker(num)
            if tmp_next is None:
                self.end = linker

            if tmp and tmp_next is None:
                tmp.next = linker
                linker.pre = tmp
            elif tmp and tmp_next:
                tmp.next = linker
                linker.pre = tmp
                linker.next = tmp_next
                tmp_next.pre = linker
            elif tmp is None and tmp_next:
                linker.next = tmp_next
                tmp_next.pre = linker

            if self.odd:
                # 从两个中位数变为一个
                if num < self.mid.v:
                    self.mid_next = None
                elif self.mid.v <= num < self.mid_next.v:
                    self.mid = self.mid.next
                    self.mid_next = None
                elif self.mid_next.v <= num:
                    self.mid = self.mid_next
                    self.mid_next = None
            else:
                # 从一个中位数变为两个
                if num < self.mid.v:
                    self.mid_next = self.mid
                    self.mid = self.mid.pre

                else:
                    self.mid_next = self.mid.next

    def findMedian(self):
        """
        :rtype: float
        """
        if not self.mid:
            return None

        if self.odd:
            return self.mid.v
        else:
            return (self.mid.v + self.mid.next.v) / 2.0

33行还是按照插入排序从末尾开始向前遍历，但是因为我们有中位数 ，那么就可以与中位数进行比较，然后减少一半的时间。

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
class MedianFinder2(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.mid = None
        self.odd = None

    def addNum(self, num):
        """
        :type num: int
        :rtype: void
        """
        if not self.mid:
            self.mid = Linker(num)
            self.mid_next = None
            self.odd = True  # 是否增加了计数个
        else:
            self.odd = not self.odd
            tmp = self.mid
            tmp_next = self.mid.next
            if num < self.mid.v:
                while tmp and tmp.v > num:
                    tmp_next = tmp
                    tmp = tmp.pre
            else:
                while tmp_next and tmp_next.v <= num:
                    tmp = tmp_next
                    tmp_next = tmp.next

            linker = Linker(num)

            if tmp and tmp_next is None:
                tmp.next = linker
                linker.pre = tmp
            elif tmp and tmp_next:
                tmp.next = linker
                linker.pre = tmp
                linker.next = tmp_next
                tmp_next.pre = linker
            elif tmp is None and tmp_next:
                linker.next = tmp_next
                tmp_next.pre = linker

            if self.odd:
                # 从两个中位数变为一个
                if num < self.mid.v:
                    self.mid_next = None
                elif self.mid.v <= num < self.mid_next.v:
                    self.mid = self.mid.next
                    self.mid_next = None
                elif self.mid_next.v <= num:
                    self.mid = self.mid_next
                    self.mid_next = None
            else:
                # 从一个中位数变为两个
                if num < self.mid.v:
                    self.mid_next = self.mid
                    self.mid = self.mid.pre

                else:
                    self.mid_next = self.mid.next

    def findMedian(self):
        """
        :rtype: float
        """
        if not self.mid:
            return None

        if self.odd:
            return self.mid.v
        else:
            return (self.mid.v + self.mid.next.v) / 2.0

修改后的还是快了一倍的时间，但是还是超时了。无法通过。

最终解法要用堆

还是用笔在纸上把问题重新描述一下吧。通常非常管用。 既然题目要求得到中位数，那么其实并没有要求对所有的数字进行排序。 而且又要快速的取得中间值，那么最大最小堆是最接近的。 往堆里插入一个数字的时间复杂度是O(lgN)，而取最小值的操作为O(1)。 总的时间复杂度是O(NlgN)。嗯，比前面的O(N**2)肯定是要快的。 但是堆只能取最大或最小的值，怎么取中间值呢？哈哈，把数字一分为二， 使用两个堆就解决了。如果数字从小到大排列，那么前一半用一个最大堆， 后一般用一个最小堆。以下是通过的代码。

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
from heapq import heappush,heappushpop
class MedianFinder3(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.a = [] # 从小到mid；最大堆
        self.b = [] # 从 mid+1 到大 ,最小堆
        self.odd = False

    def addNum(self, num):
        """
        :type num: int
        :rtype: void
        """
        self.odd = not self.odd
        if not self.b:
            self.b.append(num)
        else :
            if not self.odd :
                if num < self.b[0] :
                    heappush(self.a, -num)
                else :
                    v = heappushpop(self.b, num)
                    heappush(self.a, -v)
            else :
                if num < (-self.a[0]) :
                    v = heappushpop(self.a, -num)
                    heappush(self.b, -v)
                elif -self.a[0] <= num < self.b[0] :
                    heappush(self.b, num)
                elif self.b[0] <= num :
                    heappush(self.b, num)


    def findMedian(self):
        """
        :rtype: float
        """
        if self.odd :
            return self.b[0]
        else :
            return (-self.a[0] + self.b[0])/2.0

吐槽

python只默认实现了一个最小堆。想要一个最大堆，还得像第23行 代码那样使用一种取负数技巧。虽然heapq模块里有一个构造最大堆的方法 _heapify_max()但是却没有_heappushpop_max这样的方法。真是无语啊。