<filename>Q295.py
"""
295
find median from data stream
hard
"""


class MedianFinder:

    # TLE

    def __init__(self):
        """
        initialize your data structure here.
        """
        from collections import Counter
        self.count = Counter()
        self.total = 0
        self.unique = []

    def addNum(self, num: int) -> None:
        if num not in self.unique:
            self.unique.append(num)
        self.count[num] += 1
        self.total += 1
        return None

    def findMedian(self) -> float:
        self.unique.sort()
        if self.total % 2 == 1:
            c = 0
            for val in self.unique:
                if c + self.count[val] >= self.total // 2 + 1:
                    return val
                else:
                    c += self.count[val]
        if self.total % 2 == 0:
            c = 0
            for val in self.unique:
                if c + self.count[val] == self.total / 2:
                    left = val
                if c == self.total / 2:
                    right = val
                    return (left + right) / 2
                if c < self.total / 2 < c + self.count[val]:
                    return val
                c += self.count[val]


sol = MedianFinder()
sol.addNum(1)
print(sol.findMedian())
sol.addNum(2)
print(sol.findMedian())
<filename>Q295.py
"""
295
find median from data stream
hard
"""


class MedianFinder:

    # TLE

    def __init__(self):
        """
        initialize your data structure here.
        """
        from collections import Counter
        self.count = Counter()
        self.total = 0
        self.unique = []

    def addNum(self, num: int) -> None:
        if num not in self.unique:
            self.unique.append(num)
        self.count[num] += 1
        self.total += 1
        return None

    def findMedian(self) -> float:
        self.unique.sort()
        if self.total % 2 == 1:
            c = 0
            for val in self.unique:
                if c + self.count[val] >= self.total // 2 + 1:
                    return val
                else:
                    c += self.count[val]
        if self.total % 2 == 0:
            c = 0
            for val in self.unique:
                if c + self.count[val] == self.total / 2:
                    left = val
                if c == self.total / 2:
                    right = val
                    return (left + right) / 2
                if c < self.total / 2 < c + self.count[val]:
                    return val
                c += self.count[val]


sol = MedianFinder()
sol.addNum(1)
print(sol.findMedian())
sol.addNum(2)
print(sol.findMedian())
295 find median from data stream hard # TLE initialize your data structure here.