leetcode/python/295-Find-Median-from-Data-Stream.py at master · jjsizemore/leetcode · GitHub

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
103
104
105
106
107
108
# region Two Heaps
# This solution has a better run time than the shorter one because there are at worst 2 pushes and 1 pop during insertion
import heapq


class MedianFinder:
    def __init__(self):
        self.minHeap = []
        self.maxHeap = []

    def addNum(self, num: int) -> None:
        if not self.minHeap or num > self.minHeap[0]:
            heapq.heappush(self.minHeap, num)
            if len(self.minHeap) > len(self.maxHeap) + 1:
                elem = heapq.heappop(self.minHeap)
                heapq.heappush(self.maxHeap, -elem)
        else:
            heapq.heappush(self.maxHeap, -num)
            if len(self.maxHeap) > len(self.minHeap):
                elem = heapq.heappop(self.maxHeap)
                heapq.heappush(self.minHeap, -elem)

    def findMedian(self) -> float:
        if len(self.minHeap) == len(self.maxHeap):
            return (self.minHeap[0] - self.maxHeap[0]) * 0.5
        else:
            return self.minHeap[0]


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

# endregion

# region Two Heaps Shorter
# This solution runs slower than the one above because there are at worst 3 pushes and 2 pops during insertion, but it's more concise

import heapq


class MedianFinder:
    def __init__(self):
        self.minHeap = []
        self.maxHeap = []

    def addNum(self, num: int) -> None:
        heapq.heappush(self.minHeap, num)

        heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))

        if len(self.minHeap) < len(self.maxHeap):
            heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))

    def findMedian(self) -> float:
        if len(self.minHeap) == len(self.maxHeap):
            return (self.minHeap[0] - self.maxHeap[0]) * 0.5
        else:
            return self.minHeap[0]


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

# endregion

# region Insertion Sort


class MedianFinder:
    def __init__(self):
        self.vals = []

    def addNum(self, num: int) -> None:
        if not self.vals:
            self.vals.append(num)
        else:
            left, right = 0, len(self.vals)

            while left < right:
                mid = left + (right - left) // 2
                if self.vals[mid] > num:
                    right = mid
                else:
                    left = mid + 1

            self.vals.insert(int(left), num)

    def findMedian(self) -> float:
        size = len(self.vals)
        half = int(size // 2)

        return (
            self.vals[half]
            if size % 2
            else (self.vals[half] + self.vals[half - 1]) * 0.5
        )


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

# endregion