题目描述
这是 LeetCode 上的 1418. 点菜展示表 ，难度为 中等。
Tag : 「数据结构」、「哈希表」、「红黑树」
给你一个数组 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^4104
- orders[i].length == 3
- 1 <= customerNamei.length, foodItemi.length <= 20
- customerNamei 和 foodItemi 由大小写英文字母及空格字符 ' ' 组成。
- tableNumberi 是 1 到 500 范围内的整数。
基本分析
这是一道考虑「数据结构运用」与「简单设计」的模拟题。
我们可以根据最终的 “结果” 反推数据结构存储格式。
最终 “结果” 包含两部分：
title: 由 "Table" + 排序去重的餐品 组成- 内容 : 由 桌号 + 每件餐品对应的数量 组成
基于此，不难设计出使用 Set 存储 title 相关内容，使用 Map 存储内容相关部分。
去重 Map 的部分 Key 为桌号，同时为了快速索引当前桌号「某个餐品的数量」，需要再套一层 Map。即最终存储格式为 桌号 : {餐品 : 个数}。
HashSet & HashMap
有了基本分析，我们可以使用最常规的 HashSet 和 HashMap 进行实现。
由于 HashSet 是基于 HashMap，而 HashMap 的底层数据结构实现是 哈希表，因此我们需要在构造答案时手动排个序。
Java 代码：
class Solution { public List<List<String>> displayTable(List<List<String>> os) { List<List<String>> ans = new ArrayList<>(); // 桌号 : {餐品 : 个数}（用于构造内容） Map<Integer, Map<String, Integer>> tm = new HashMap<>(); // 餐品（用于构造 title） Set<String> ts = new HashSet<>(); for (List<String> o : os) { String c = o.get(0), t = o.get(1), f = o.get(2); Integer tidx = Integer.parseInt(t); ts.add(f); Map<String, Integer> map = tm.getOrDefault(tidx, new HashMap<>()); map.put(f, map.getOrDefault(f, 0) + 1); tm.put(tidx, map); } int n = tm.size() + 1, m = ts.size() + 1; // 构造 title & 手动排序 List<String> foods = new ArrayList<>(ts); Collections.sort(foods); List<String> title = new ArrayList<>(); title.add("Table"); title.addAll(foods); ans.add(title); // 构造内容 & 手动排序 List<Integer> tables = new ArrayList<>(tm.keySet()); Collections.sort(tables); for (int tidx : tables) { Map<String, Integer> map = tm.get(tidx); List<String> cur = new ArrayList<>(); cur.add(tidx + ""); for (String food : foods) { cur.add(map.getOrDefault(food, 0) + ""); } ans.add(cur); } return ans; } } 复制代码
Python3 代码：
class Solution: def displayTable(self, orders: List[List[str]]) -> List[List[str]]: ans = [] # 桌号 : {餐品 : 个数}（用于构造内容） tm = defaultdict(lambda: defaultdict(int)) # 餐品（用于构造 title） ts = set() for c,t,f in orders: tidx = int(t) ts.add(f) tm[tidx][f] += 1 n, m = len(tm) + 1, len(ts) + 1 # 构造 title & 手动排序 foods = sorted(ts) title = [] title.append("Table") title += foods ans.append(title) # 构造内容 & 手动排序 for tidx in sorted(tm.keys()): cur = [] cur.append(str(tidx)) for food in foods: cur.append(str(tm[tidx][food])) ans.append(cur) return ans 复制代码
- 时间复杂度：
HashSet和HashMap的基本操作都是 O(1)O(1)。预处理所有的订单复杂度为 O(n)O(n)；去重后的桌数为 rr，餐品数量为 cc，对两者排序的复杂度分别为 O(r\log{r})O(rlogr) 和 O(c\log{c})O(clogc)；构造答案复杂度为 O(r * c)O(r∗c)；最终复杂度为 O(\max(n, r\log{r}, c\log{c}, r * c))O(max(n,rlogr,clogc,r∗c)) - 空间复杂度：O(r + c + r * c)O(r+c+r∗c)
TreeSet & TreeMap
与 HashSet 和 HashMap 的关系类似，TreeSet 是基于 TreeMap 实现的，而 TreeMap 底层数据结构实现是 红黑树。
得益于 Java 的「面向接口编程（IOP）」设计，我们可以毫不费力的将解法一中的 HashSet 替换成 TreeSet、将 HashMap 替换成 TreeMap，并删除手动排序相关代码，得到我们的解法二。
利用 TreeMap 的默认排序规则（数值升序、非数值字典序升序）来简化我们的实现。
但需要注意的是，利用 TreeMap 的内部有序特性，调整操作可能会发生在每一次插入操作中，而解法一则是利用 Collections.sort 进行一次性的排序，对于非自定义类 Collections.sort 是基于 Arrays.sort 实现的，会根据「数组大小」、「数组本身是否大致有序」等因素综合决定最终的排序方案，在数据完全随机的情况下，执行效率很大程度要优于 TreeMap 的多次调整，但两者复杂度都是 O(n\log{n})O(nlogn)。
因此在所有数据都提前给定的「离线」情况下，其实更推荐使用解法一。
Java 代码：
class Solution { public List<List<String>> displayTable(List<List<String>> os) { List<List<String>> ans = new ArrayList<>(); // 桌号 : {餐品 : 个数}（用于构造内容） Map<Integer, Map<String, Integer>> tm = new TreeMap<>(); // 餐品（用于构造 title） Set<String> ts = new TreeSet<>(); for (List<String> o : os) { String c = o.get(0), t = o.get(1), f = o.get(2); Integer tidx = Integer.parseInt(t); ts.add(f); Map<String, Integer> map = tm.getOrDefault(tidx, new HashMap<>()); map.put(f, map.getOrDefault(f, 0) + 1); tm.put(tidx, map); } int n = tm.size() + 1, m = ts.size() + 1; // 构造 title List<String> title = new ArrayList<>(); title.add("Table"); title.addAll(ts); ans.add(title); // 构造内容 for (int tidx : tm.keySet()) { Map<String, Integer> map = tm.get(tidx); List<String> cur = new ArrayList<>(); cur.add(tidx + ""); for (String food : ts) { cur.add(map.getOrDefault(food, 0) + ""); } ans.add(cur); } return ans; } } 复制代码
Python3 代码：
from sortedcontainers import SortedSet, SortedDict class Solution: def displayTable(self, orders: List[List[str]]) -> List[List[str]]: ans = [] # 桌号 : {餐品 : 个数}（用于构造内容） tm = SortedDict() # 餐品（用于构造 title） ts = SortedSet() for c,t,f in orders: tidx = int(t) ts.add(f) if tidx not in tm: tm[tidx] = defaultdict(int) tm[tidx][f] += 1 n, m = len(tm) + 1, len(ts) + 1 # 构造 title title = ["Table"] title += list(ts) ans.append(title) # 构造内容 for tidx, cnts in tm.items(): cur = [str(tidx)] for food in ts: cur.append(str(cnts[food])) ans.append(cur) return ans 复制代码
- 时间复杂度：
TreeSet和TreeMap的基本操作都是 O(log{k})O(logk)。预处理所有的订单复杂度为 O(n\log{n})O(nlogn)；去重后的桌数为 rr，餐品数量为 cc，构造答案复杂度为 O(r\log{r} * c\log{c})O(rlogr∗clogc)；最终复杂度为 O(\max(n\log{n}, r\log{r} * c\log{c}))O(max(nlogn,rlogr∗clogc)) - 空间复杂度：O(r + c + r * c)O(r+c+r∗c)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1418 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
