难度: Medium
Submission
运行时间: 107 ms
内存: 28.8 MB
class SQL:
def __init__(self, names: List[str], columns: List[int]):
self.seeds = defaultdict(int)
self.grid = defaultdict(dict)
def insertRow(self, name: str, row: List[str]) -> None:
self.seeds[name] += 1
rowId = self.seeds[name]
self.grid[name][rowId] = row
def deleteRow(self, name: str, rowId: int) -> None:
self.grid[name].pop(rowId)
def selectCell(self, name: str, rowId: int, columnId: int) -> str:
return self.grid[name][rowId][columnId-1]
# Your SQL object will be instantiated and called as such:
# obj = SQL(names, columns)
# obj.insertRow(name,row)
# obj.deleteRow(name,rowId)
# param_3 = obj.selectCell(name,rowId,columnId)
Explain
这个题解通过模拟一个简单的数据库来存储和管理数据行。每一个SQL对象可以管理多个表格，其中每个表格由一个名称标识。使用两个主要的数据结构：一个字典来记录每个表的行ID种子（自增的行ID），另一个嵌套字典来存储表格数据，其中外层字典的键是表名，内层字典的键是行ID，值是对应的行数据（列表形式）。'insertRow'方法用于在指定的表中插入新行，并自动分配行ID；'deleteRow'方法用于删除指定表的指定行；'selectCell'方法用于获取特定表、行和列的单元格数据。
时间复杂度: O(1)
空间复杂度: O(N + M)
class SQL:
def __init__(self, names: List[str], columns: List[int]):
self.seeds = defaultdict(int) # 每个表的行ID种子
self.grid = defaultdict(dict) # 存储所有表的数据
def insertRow(self, name: str, row: List[str]) -> None:
self.seeds[name] += 1 # 为新行生成行ID
rowId = self.seeds[name]
self.grid[name][rowId] = row # 插入行数据到指定表
def deleteRow(self, name: str, rowId: int) -> None:
self.grid[name].pop(rowId) # 从指定表删除指定行
def selectCell(self, name: str, rowId: int, columnId: int) -> str:
return self.grid[name][rowId][columnId-1] # 访问特定表的特定行和列的数据
Explore
在模拟SQL类中使用字典来存储表和行数据的主要原因是字典提供了高效的键值对映射，这使得数据的插入、查找和删除操作都能以接近O(1)的时间复杂度进行。相比之下，如果使用列表，那么查找和删除操作通常需要O(n)的时间复杂度，而树形结构虽然可以提供较好的排序和搜索性能（通常是O(log n)），但在处理如自增ID这样的简单键值对映射时，其额外的结构复杂性并不提供明显优势。因此，字典因其简单性和效率成为更佳选择。
题解中的设计没有直接考虑并发插入的情况。在单线程环境下，自增行ID能保持唯一性和一致性。然而，在多线程或并发环境下，若多个线程同时调用'insertRow'方法，可能会导致行ID重复或数据竞争问题。为了处理并发环境，需要引入锁机制或使用线程安全的数据结构来确保行ID的唯一性和操作的原子性。
在当前实现中，`deleteRow`方法通过调用字典的`pop`方法来尝试移除指定的行ID。如果指定的行ID不存在，`pop`方法会引发KeyError异常。这个异常可以被捕获并处理，例如返回一个错误消息或忽略。在实际应用中，通常会在删除前检查行ID是否存在，以避免不必要的异常处理。
根据题解中的描述，如果在`insertRow`和`deleteRow`方法中指定的表名不存在，由于使用了`defaultdict`来存储表和行数据，当尝试访问一个不存在的键时，`defaultdict`会自动创建这个键并将其映射到一个新的字典。在`insertRow`中，这意味着会自动创建一个新表，并在其中插入行数据。在`deleteRow`中，如果表名不存在，会创建一个空字典，但由于没有行数据要删除，所以这个操作实际上不会有任何副作用。