【每日算法】比较哈希表与红黑树两种实现（哈希表的查找算法）

【每日算法】比较哈希表与红黑树两种实现（哈希表的查找算法）

题目描述

这是 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,Water3 ,0 ,2 ,1 ,05 ,0 ,1 ,0 ,110 ,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 == 31 <= customerNamei.length, foodItemi.length <= 20customerNamei 和 foodItemi 由大小写英文字母及空格字符 ' ' 组成。tableNumberi 是 1 到 500 范围内的整数。

基本分析

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

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

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

​​title​​ : 由"Table" + 排序去重的餐品组成内容 : 由桌号 + 每件餐品对应的数量组成

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

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

HashSet & HashMap

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

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

Java 代码：

class Solution { public List> displayTable(List> os) { List> ans = new ArrayList<>(); // 桌号 : {餐品 : 个数}（用于构造内容） Map> tm = new HashMap<>(); // 餐品（用于构造 title） Set ts = new HashSet<>(); for (List o : os) { String c = o.get(0), t = o.get(1), f = o.get(2); Integer tidx = Integer.parseInt(t); ts.add(f); Map 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 foods = new ArrayList<>(ts); Collections.sort(foods); List title = new ArrayList<>(); title.add("Table"); title.addAll(foods); ans.add(title); // 构造内容 & 手动排序 List tables = new ArrayList<>(tm.keySet()); Collections.sort(tables); for (int tidx : tables) { Map map = tm.get(tidx); List 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> displayTable(List> os) { List> ans = new ArrayList<>(); // 桌号 : {餐品 : 个数}（用于构造内容） Map> tm = new TreeMap<>(); // 餐品（用于构造 title） Set ts = new TreeSet<>(); for (List o : os) { String c = o.get(0), t = o.get(1), f = o.get(2); Integer tidx = Integer.parseInt(t); ts.add(f); Map 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 title = new ArrayList<>(); title.add("Table"); title.addAll(ts); ans.add(title); // 构造内容 for (int tidx : tm.keySet()) { Map map = tm.get(tidx); List 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 原题链接和其他优选题解。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。