题目描述
这是 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 *
- orders[i].length == 3
- 1 <= customerNamei.length, foodItemi.length <= 20
- customerNamei 和 foodItemi 由大小写英文字母及空格字符 ' ' 组成。
- tableNumberi 是 1 到 500 范围内的整数。
基本分析
这是一道考虑「数据结构运用」与「简单设计」的模拟题。
我们可以根据最终的 “结果” 反推数据结构存储格式。
最终 “结果” 包含两部分：
基于此，不难设计出使用 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 的基本操作都是。预处理所有的订单复杂度为；去重后的桌数为，餐品数量为，对两者排序的复杂度分别为和；构造答案复杂度为；最终复杂度为
- 空间复杂度：
TreeSet & TreeMap
与 HashSet 和 HashMap 的关系类似，TreeSet 是基于 TreeMap 实现的，而 TreeMap 底层数据结构实现是 红黑树。
得益于 Java 的「面向接口编程（IOP）」设计，我们可以毫不费力的将解法一中的 HashSet 替换成 TreeSet、将 HashMap 替换成 TreeMap，并删除手动排序相关代码，得到我们的解法二。
利用 TreeMap 的默认排序规则（数值升序、非数值字典序升序）来简化我们的实现。
但需要注意的是，利用 TreeMap 的内部有序特性，调整操作可能会发生在每一次插入操作中，而解法一则是利用 Collections.sort 进行一次性的排序，对于非自定义类 Collections.sort 是基于 Arrays.sort 实现的，会根据「数组大小」、「数组本身是否大致有序」等因素综合决定最终的排序方案，在数据完全随机的情况下，执行效率很大程度要优于 TreeMap 的多次调整，但两者复杂度都是 。
因此在所有数据都提前给定的「离线」情况下，其实更推荐使用解法一。
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, SortedDictclass 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 的基本操作都是。预处理所有的订单复杂度为；去重后的桌数为，餐品数量为，构造答案复杂度为；最终复杂度为
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1418 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。