首页 > 试题广场 >

设计有setAll功能的哈希表

[编程题]设计有setAll功能的哈希表

热度指数：1250 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

哈希表常见的三个操作时put、get和containsKey，而且这三个操作的时间复杂度为O(1)。现在想加一个setAll功能，就是把所有记录value都设成统一的值。请设计并实现这种有setAll功能的哈希表，并且put、get、containsKey和setAll四个操作的时间复杂度都为O(1)。

[友情提示]: C++选手若有需要可以使用unordered_map替换map来将复杂度从O(log n)降为O(1)

输入描述:

第一行一个整数N表示操作数。
接下来N行，每行第一个数字opt代表操作类型
若opt=1，接下来有两个整数x, y表示设置key=x对应的value=y
若opt=2，接下来一个整数x，表示查询key=x对应的value，若key=x不存在输出-1
若opt=3，接下来一个整数x，表示把加入过的所有的key对应的value都设置为x

输出描述:

对于每个操作2，输出一个整数表示答案

示例1

输入

输出

2
-1
4
-1

备注:

算法知识视频讲解

Python

ImbaPlayer

class MyHash:
    def __init__(self) -> None:
        self.map = {}
        self.memory = set()
        self.all_val = 0
    def put(self, key, val):
        self.map[key] = val
        self.memory.add(key)

    def get(self, key):
        if key in self.map:
            return self.map[key]
        elif key in self.memory:
            return self.all_val
        else:
            return -1
    def set_all(self, val):
        self.map.clear()
        self.all_val = val

def main():
    myhash = MyHash()
    N = int(input())
    for _ in range(N):
        tmp_list = list(map(int, input().split()))
        if tmp_list[0] == 1:
            myhash.put(tmp_list[1], tmp_list[2])
        elif tmp_list[0] == 2:
            print(myhash.get(tmp_list[1]))
        else:
            myhash.set_all(tmp_list[1])
main()

发表于 2022-05-08 13:10:36 回复(0)