LC 1418. 点菜展示表

题目描述

这是 LeetCode 上的 1418. 点菜展示表 ，难度为 中等。

给你一个数组 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 范围内的整数。

---

基本分析

这是一道考虑「数据结构运用」与「简单设计」的模拟题。

我们可以根据最终的 “结果” 反推数据结构存储格式。

最终 “结果” 包含两部分：

1. title : 由 “Table” + 排序去重的餐品 组成
2. 内容 : 由 桌号 + 每件餐品对应的数量 组成

基于此，不难设计出使用 Set 存储 title 相关内容，使用 Map 存储内容相关部分。

去重 Map 的部分 Key 为桌号，同时为了快速索引当前桌号「某个餐品的数量」，需要再套一层 Map。即最终存储格式为 桌号 : {餐品 : 个数}。

---

HashSet & HashMap

有了基本分析，我们可以使用最常规的 HashSet 和 HashMap 进行实现。

由于 HashSet 是基于 HashMap，而 HashMap 的底层数据结构实现是 哈希表，因此我们需要在构造答案时手动排个序。

代码：

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;
    }
}

• 时间复杂度：HashSet 和 HashMap 的基本操作都是 $O(1)$。预处理所有的订单复杂度为 $O(n)$；去重后的桌数为 $r$，餐品数量为 $c$，对两者排序的复杂度分别为 $O(r\log{r})$ 和 $O(c\log{c})$；构造答案复杂度为 $O(r c)$；最终复杂度为 $O(\max(n, r\log{r}, c\log{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})$。

因此在所有数据都提前给定的「离线」情况下，其实更推荐使用解法一。

代码：

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;
    }
}

• 时间复杂度：TreeSet 和 TreeMap 的基本操作都是 $O(log{k})$。预处理所有的订单复杂度为 $O(n\log{n})$；去重后的桌数为 $r$，餐品数量为 $c$，构造答案复杂度为 $O(r\log{r} c\log{c})$；最终复杂度为 $O(\max(n\log{n}, r\log{r} c\log{c}))$
• 空间复杂度：$O(r + c + r * c)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1418 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。