顺序容器的爱

国庆节的前一天，天气突然变得凉爽起来，心情也还算不错。我继续在Leetcode里寻觅那命中的一题。这不正巧，碰到了9月30日的每日一题。
1845. 座位预约管理系统
我抱着试一试的态度，趁机检验一下原生API的性能。结果发现使用rassoc和key都不能通过，因为时间复杂度是O(n)
如下是key方法

class SeatManager

=begin
    :type n: Integer
=end
    def initialize(n)
      @h = (1..n).to_h {|it| [it,true]}
    end


=begin
    :rtype: Integer
=end
    def reserve()
      ans = @h.key(true) 
      @h[ans] = false
      ans
    end


=begin
    :type seat_number: Integer
    :rtype: Void
=end
    def unreserve(seat_number)
      @h[seat_number] = true   
    end


end

如下是rassoc的方法

class SeatManager

=begin
    :type n: Integer
=end
    def initialize(n)
      @h = (1..n).to_h {|it| [it,true]}
      @cnt = 0
    end


=begin
    :rtype: Integer
=end
    def reserve()
      if @cnt == 0
        ans = 1
        @h[ans] = nil
        @cnt += 1
        return ans
      else
        ans = @h.rassoc(true)[0]
        @h[ans] = nil
        @cnt += 1
        return ans
      end
    end


=begin
    :type seat_number: Integer
    :rtype: Void
=end
    def unreserve(seat_number)
      @h[seat_number] = true   
    end


end

上述两个Ruby解都会TL
这个时候也不知道脑海里浮现出了怎样一幅光景，想到了Python的顺序容器，于是一切变得豁然开朗，整个世界都变得简单起来了。

from sortedcontainers import SortedList
class SeatManager:

    def __init__(self, n: int):
        self.l = SortedList([i for i in range(1,n+1,1)])
        self.cnt = 0
    def reserve(self) -> int:
        if self.cnt == 0:
            ans = 1
            self.l.discard(ans)
            self.cnt += 1
            return ans
        else:
            ans = self.l[0]
            self.l.discard(ans)
            return ans
    def unreserve(self, seatNumber: int) -> None:
        self.l.add(seatNumber)


# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)

然后乘势而上，AC了Leetcode 295
295. 数据流的中位数

from sortedcontainers import SortedList
class MedianFinder:

    def __init__(self):
        self.h = SortedList([])

    def addNum(self, num: int) -> None:
        self.h.add(num)

    def findMedian(self) -> float:
        if len(self.h)%2 == 1:
          return self.h[len(self.h)//2]
        else:
          return (self.h[len(self.h)//2]+self.h[len(self.h)//2 - 1])/2


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

这也许就是顺序容器的爱吧，期待着Ruby某一天也会有这个feature。
写在最后，我还是希望自己忘了爱吧。