韩国

最近韩国最火的新闻，是三星和海力士，年度预计营收破万亿。

两家企业的员工，预计人均年度奖金会去到大几亿韩元，折算人民币大几百万。

一定程度，甚至刺激了韩国的相亲市场。

那些就职于海力士/三星的单身人士，最近电话都被打爆了，一跃成为了社会认可度极高的人群。

要知道，韩国可是全球结婚率最低的国家之一。像"相亲市场火爆"这种新闻，再过去十几年都没听说过。

果然，好的经济能解决大多数社会问题，少数尚未解决的，通常只需要更好的经济。

说到这里，可能还有人对这两家公司的爆炸业绩没有概念。

这么算吧，两家企业净利润加起来 88 万亿韩元，而韩国总人口 5000 万出头。

两家公司的利润，按人头平分，每人能分 1700 万韩元，折合人民币接近 10 万。

两家公司的净利润，能给全国人民发人均 10 万的红包，你想想 ...

估计有韩国的政策高层也算了这笔账，开始在社交平台发表言论：AI 产业的超额利润应返还全民，提议设立"公民红利"：

这位韩国政策高层的主要观点是："人工智能基础设施时代的收益，并非仅由个别企业创造，而是源于整个国家在过去半个多世纪中所构建的产业基础。因此，这些收益中的一部分应通过制度安排回馈给全体国民。"

想都不用想，这种帖子一出，除了三星和海力士，估计全国人民都举手同意。

但有意义吗，我觉得意义不大。

你可以要求企业纳税，或者投资基建，但这么赤裸裸说要给全国人民发钱，完全不可能的事情。

就算是全球 AI 金铲子厂商的「英伟达」，也没有过这样的先例，韩国的三星和海力士更不可能。

...

聊到这里，来一道和「字节跳动」相关的算法题。

题目描述

平台：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 *
• 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 的基本操作都是 。预处理所有的订单复杂度为 ；去重后的桌数为 ，餐品数量为 ，对两者排序的复杂度分别为 和 ；构造答案复杂度为 ；最终复杂度为
• 空间复杂度：

TreeSet & TreeMap

与 HashSet 和 HashMap 的关系类似，TreeSet 是基于 TreeMap 实现的，而 TreeMap 底层数据结构实现是 「红黑树」。

「得益于 Java 的「面向接口编程（IOP）」设计，我们可以毫不费力的将解法一中的 HashSet 替换成 TreeSet、将 HashMap 替换成 TreeMap，并删除手动排序相关代码，得到我们的解法二。」

利用 TreeMap 的默认排序规则（数值升序、非数值字典序升序）来简化我们的实现。

但需要注意的是，利用 TreeMap 的内部有序特性，调整操作可能会发生在每一次插入操作中，而解法一则是利用 Collections.sort 进行一次性的排序，对于非自定义类 Collections.sort 是基于 Arrays.sort 实现的，会根据「数组大小」、「数组本身是否大致有序」等因素综合决定最终的排序方案，在数据完全随机的情况下，执行效率很大程度要优于 TreeMap 的多次调整，但两者复杂度都是 。

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

代码：

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 的基本操作都是 。预处理所有的订单复杂度为 ；去重后的桌数为 ，餐品数量为 ，构造答案复杂度为 ；最终复杂度为
• 空间复杂度：

最后

巨划算的 LeetCode 会员优惠通道目前仍可用 ~

使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。

我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。