题解 | 【模板】多重集合操作

【模板】多重集合操作

https://www.nowcoder.com/practice/aaf8b53f6ea74ad6beabed77bb275725

from collections import defaultdict
from bisect import insort, bisect_left, bisect_right


class MultiSet:
    def __init__(self):
        self._set = defaultdict(int)
        self._vec = []
        self._size = 0

    def insert_value(self, x: int) -> None:
        """Insert a value into the multiset."""
        self._size += 1
        if self._set[x] == 0:
            insort(self._vec, x)
        self._set[x] += 1

    def erase_value(self, x: int) -> None:
        """Erase one occurrence of a value from the multiset."""
        if self._set[x] > 0:
            self._size -= 1
            self._set[x] -= 1
            if self._set[x] == 0:
                self._vec.pop(bisect_left(self._vec, x))

    def count(self, x: int) -> int:
        """Return the count of x in the multiset."""
        return self._set[x]

    def size(self) -> int:
        """Return the total size of the multiset."""
        return self._size

    def get_predecessor(self, x: int) -> int:
        """Return the predecessor of x or -1 if none exists."""
        index = bisect_left(self._vec, x)
        return -1 if index == 0 else self._vec[index - 1]

    def get_successor(self, x: int) -> int:
        """Return the successor of x or -1 if none exists."""
        index = bisect_right(self._vec, x)
        return -1 if index == len(self._vec) else self._vec[index]


def main():
    multiset = MultiSet()
    q = int(input())
    for _ in range(q):
        line = map(int, input().split())
        cnt, op, x = 0, 0, 0
        for i in line:
            if cnt == 0:
                op = i
            else: 
                x = i
            cnt += 1
        
        if op == 1:
            multiset.insert_value(x)
        elif op == 2:
            multiset.erase_value(x)
        elif op == 3:
            print(multiset.count(x))
        elif op == 4:
            print(multiset.size())
        elif op == 5:
            print(multiset.get_predecessor(x))
        elif op == 6:
            print(multiset.get_successor(x))


if __name__ == "__main__":
    main()

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:22
怎么这么多逆天求职者,救救我救救我救救我😭
flmz_Kk:哈哈哈哈哈哈,这么多求职者,肯定有那一两个逆天的
点赞 评论 收藏
分享
07-09 15:55
门头沟学院 Java
点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务