在 Class 问题中从数据流 init 中查找中位数

Question

我有一个关于在 class 中定义 init 的问题。原来的问题是：

Design a class to calculate the median of a number stream. The class should have the following two methods:

insertNum(int num): stores the number in the class findMedian(): returns the median of all numbers inserted in the class If the count of numbers inserted in the class is even, the median will be the average of the middle two numbers.

我的原码是：

from heapq import *


class Solution:
    # define the min and max heaps
    def __init__(self):
        self.minHeap = []
        self.maxHeap = []

    def insertNum(self, num):
        # check if the first number into the heap
        # use -num to create the max heap
        if not self.maxHeap or num <= -self.maxHeap[0]:
            heappush(self.maxHeap, -num)
        else:
            heappush(self.minHeap, num)
        print(self.minHeap, self.maxHeap)
        # ensure l(maxHeap) = l(minHeap) or +1
        # 4 vs 2
        if len(self.maxHeap) > len(self.minHeap) + 1:
            heappush(self.minHeap, -heappop(self.maxHeap))
        # 1 vs 2
        elif len(self.maxHeap) < len(self.minHeap):
            heappush(self.maxHeap, -heappop(self.minHeap))
        print(self.minHeap, self.maxHeap)

    def findMedian(self):
        print(self.minHeap, self.maxHeap)
        if len(self.minHeap) == len(self.maxHeap):
            return 0.5 * (self.minHeap[0] - self.maxHeap[0])
        if len(self.maxHeap) == len(self.minHeap) + 1:
            return -self.maxHeap[0]


def main():
    Solution().insertNum(3)
    Solution().insertNum(1)
    print("The median is: " + str(Solution().findMedian()))
    Solution().insertNum(5)
    print("The median is: " + str(Solution().findMedian()))
    Solution().insertNum(4)
    print("The median is: " + str(Solution().findMedian()))


main()

它会return以下输出：

[] [-3]
[] [-3]
[] [-1]
[] [-1]
[] []
Traceback (most recent call last):
  File "/Users/tairanye/PycharmProjects/tester/main.py", line 45, in <module>
    main()
  File "/Users/tairanye/PycharmProjects/tester/main.py", line 38, in main
    print("The median is: " + str(Solution().findMedian()))
  File "/Users/tairanye/PycharmProjects/tester/main.py", line 30, in findMedian
    return 0.5 * (self.minHeap[0] - self.maxHeap[0])
IndexError: list index out of range

Process finished with exit code 1

我认为这里的主要问题是每次调用 insertNumber 时 minHeap 和 maxHeap 都会重置。一旦我如下更新了初始代码行，问题就会解决。

class Solution:
    # define the min and max heaps

    minHeap = []
    maxHeap = []

    def insertNum(self, num):

我不确定这背后的原因。感谢您的帮助。

Answer 1

您的 class 定义似乎没问题。但是在您的 main 函数中使用 Solution() 是错误的。 Solution 是一个 class 类型，每次调用 Solution() 时，它都会创建一个新的 object/instance。即使您已经运行

Solution().insertNum(3)
Solution().insertNum(1)

之前

print("The median is: " + str(Solution().findMedian()))

然而最后一行代码Solution()没有存储数据。它们是非常不同的对象（或者后者重写了之前的对象）。因为每次调用Solution()都会创建另一个对象，很明显报错是抱怨self.minHeap中没有数据，所以调用self.minHeap[0]会导致IndexError: list index out of range错误。希望到目前为止，您清楚此错误消息的原因。

现在我们来谈谈为什么下面的代码可以正常工作。

class Solution:
    # define the min and max heaps

    minHeap = []
    maxHeap = []

    def insertNum(self, num):

现在你已经定义了

minHeap = []
maxHeap = []

作为 class 变量而不是实例变量（用 self 定义）。因此，当您每次调用 Solution() 时，即使创建了一个新实例，但数据将存储为 class 变量，并且它们将与 class 一起使用，直到 class被摧毁了。

下面两行代码将数据存入class，而不是Solution()

创建的实例

Solution().insertNum(3)
Solution().insertNum(1)

这就是为什么以后运行

print("The median is: " + str(Solution().findMedian()))

没有错误，因为 Solution() 创建的新实例在创建时已经有数据。

在 Class 问题中从数据流 init 中查找中位数

Find Median from Data Stream init in Class issue

python

heap

containers

list

global-variables

在 Class 问题中从数据流 __init__ 中查找中位数

Find Median from Data Stream __init__ in Class issue

python

heap

containers

list

global-variables

在 Class 问题中从数据流 init 中查找中位数

Find Median from Data Stream init in Class issue