点菜展示表

标签: 数组 哈希表 字符串 有序集合 排序

难度: Medium

给你一个数组 orders，表示客户在餐厅中完成的订单，确切地说， orders[i]=[customerNamei,tableNumberi,foodItemi] ，其中 customerNamei 是客户的姓名，tableNumberi 是客户所在餐桌的桌号，而 foodItemi 是客户点的餐品名称。

请你返回该餐厅的 点菜展示表 。在这张表中，表中第一行为标题，其第一列为餐桌桌号 “Table” ，后面每一列都是按字母顺序排列的餐品名称。接下来每一行中的项则表示每张餐桌订购的相应餐品数量，第一列应当填对应的桌号，后面依次填写下单的餐品数量。

注意：客户姓名不是点菜展示表的一部分。此外，表中的数据行应该按餐桌桌号升序排列。

示例 1：

输入：orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
输出：[["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]] 
解释：
点菜展示表如下所示：
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
对于餐桌 3：David 点了 "Ceviche" 和 "Fried Chicken"，而 Rous 点了 "Ceviche"
而餐桌 5：Carla 点了 "Water" 和 "Ceviche"
餐桌 10：Corina 点了 "Beef Burrito"

示例 2：

输入：orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]
输出：[["Table","Canadian Waffles","Fried Chicken"],["1","2","0"],["12","0","3"]] 
解释：
对于餐桌 1：Adam 和 Brianna 都点了 "Canadian Waffles"
而餐桌 12：James, Ratesh 和 Amadeus 都点了 "Fried Chicken"

示例 3：

输入：orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
输出：[["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]

提示：

  • 1 <= orders.length <= 5 * 10^4
  • orders[i].length == 3
  • 1 <= customerNamei.length, foodItemi.length <= 20
  • customerNamei 和 foodItemi 由大小写英文字母及空格字符 ' ' 组成。
  • tableNumberi 是 1 到 500 范围内的整数。

Submission

运行时间: 302 ms

内存: 26.5 MB

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        dic1=defaultdict(lambda:Counter())
        set2=defaultdict(set)
        for i,row in enumerate(orders):
            for caiming in row[2:]:
                set2[caiming].add(row[1])
                dic1[row[1]][caiming]+=1
        title=sorted(set2.keys())
        d=Counter()
        for i,k in enumerate(title,1):
            d[k]=i
        res=[]
        for k,row in dic1.items():
            newrow=['0']*(len(title)+1)
            newrow[0]=str(k)
            for caiming,v in row.items():
                newrow[d[caiming]]=str(int(newrow[d[caiming]])+v)
            res.append(newrow)
            
        res.sort(key=lambda x:int(x[0]))
        
        return [['Table']+title]+res

Explain

这个题解采用了哈希表的方法来解决点菜展示表问题。首先使用一个字典 dic1，其中键是桌号，值是另一个Counter，用来统计每张桌子每种食物的数量。另一个字典 set2用来记录每种食物出现在哪些桌号，以方便排序和生成标题行。遍历订单列表，更新这两个字典的信息。之后将食物种类按字典序排序，形成标题行。接着，为每个桌号生成一个数组，数组中包含该桌所有食物的点单数量。最后，将结果列表按桌号排序，并在其前添加标题行。

时间复杂度: O(F log F + T * F)

空间复杂度: O(T * F + N)

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        dic1=defaultdict(lambda: Counter())  # dic1用来存储每张桌子的点菜记录
        set2=defaultdict(set)  # set2用于记录每种食物出现在哪些桌号上
        for i, row in enumerate(orders):
            for caiming in row[2:]:  # 每个订单处理食物名称
                set2[caiming].add(row[1])  # 记录食物出现的桌号
                dic1[row[1]][caiming] += 1  # 在对应桌号增加该食物的计数
        title = sorted(set2.keys())  # 排序食物种类生成标题行
        d = Counter()  # d记录食物名称对应的列位置
        for i, k in enumerate(title, 1):
            d[k] = i
        res = []
        for k, row in dic1.items():
            newrow = ['0'] * (len(title) + 1)  # 为每个桌号创建一个新行，初始化点单数量
            newrow[0] = str(k)  # 设置桌号
            for caiming, v in row.items():
                newrow[d[caiming]] = str(int(newrow[d[caiming]]) + v)  # 更新该桌的点单数量
            res.append(newrow)  # 加入到结果列表中
        res.sort(key=lambda x: int(x[0]))  # 根据桌号排序
        return [['Table'] + title] + res  # 添加标题行并返回结果

Explore

在题解中使用`defaultdict`和`Counter`可以简化数据记录和统计的操作。`defaultdict`允许自动初始化任何新的键值对，避免了检查和创建新键的额外代码。而`Counter`是专门用于计数的数据结构，可以很方便地对每种食物的点单数量进行累加。这种组合使得算法在处理订单时更加简洁和高效。

对食物种类进行字典序排序后，食物名称将按照字典顺序出现在点菜展示表的标题行中。这不仅使得最终的展示表在视觉上更有序和一致，也便于用户查找特定食物。排序后的标题行决定了每列数据对应的食物，确保了数据的准确对齐和呈现。

`dic1`和`set2`分别存储不同类型的信息，其中`dic1`存储每张桌子的具体点菜数据（桌号到食物的映射和数量），而`set2`用于记录每种食物出现的所有桌号（食物到桌号的映射），这有助于字典序排序食物名称时快速访问所有相关桌号。这种数据结构的分离使得数据处理更具逻辑性，便于后续的操作如排序和生成显示表。

在排序过程中，通过将桌号从字符串形式转换为整型来进行比较，这保证了桌号的排序是按照数值顺序进行的，而不是按照字符串顺序。这对于确保桌号'10'排在'2'之后是必要的，因为在字符串排序中'10'会错误地排在'2'之前。通过这种方式，可以确保最终的展示表中桌号的顺序是正确的。