一、题目

给你一个数组 orders，表示客户在餐厅中完成的订单，确切地说， orders[i]=[customerNamei,tableNumberi,foodItemi] ，其中 customerNamei 是客户的姓名，tableNumberi是客户所在餐桌的桌号，而 foodItemi 是客户点的餐品名称。

请你返回该餐厅的 点菜展示表 。在这张表中，表中第一行为标题，其第一列为餐桌桌号 “Table”，后面每一列都是按字母顺序排列的餐品名称。接下来每一行中的项则表示每张餐桌订购的相应餐品数量，第一列应当填对应的桌号，后面依次填写下单的餐品数量。

注意：客户姓名不是点菜展示表的一部分。此外，表中的数据行应该按餐桌桌号升序排列。

点击查看原题
难度级别： 中等

二、思路

1）哈希表

三、代码

1）哈希表

  1. class Solution {
  2.     public List<List<String>> displayTable(List<List<String>> orders) {
  3.         List<List<String>> ans = new ArrayList();
  4.         // 记录每张桌子id点的所有菜
  5.         Map<Integer, Map<String, Integer>> tableOrder = new HashMap(orders.size() * 2);
  6.         Map<String, Integer> dishesName = new HashMap();    // 记录出现过的所有菜名，后面可以使用其记录每一桌点菜数量
  7.         for (List<String> order : orders) {    // 遍历并记录
  8.             int table = Integer.valueOf(order.get(1));
  9.             if (!tableOrder.containsKey(table)) {
  10.                 tableOrder.put(table, new HashMap<String, Integer>());
  11.             }
  12.             if (!dishesName.containsKey(order.get(2))) {
  13.                 dishesName.put(order.get(2), 0);
  14.             }
  15.             Map<String, Integer> booked = tableOrder.get(table);
  16.             booked.put(order.get(2), booked.getOrDefault(order.get(2), 0) + 1);
  17.         }
  18.         List<Map.Entry<Integer, Map<String, Integer>>> sortedTableOrder = new ArrayList(tableOrder.entrySet());
  19.         // 对每张桌子的订单进行排序，根据桌子id从小到大排列
  20.         Collections.sort(sortedTableOrder, (Map.Entry<Integer, Map<String, Integer>> m1, Map.Entry<Integer, Map<String, Integer>> m2) -> {
  21.             return m1.getKey() < m2.getKey() ? -1 : 1;
  22.         });
  23.         List<Map.Entry<String, Integer>> sortedDishesName = new ArrayList(dishesName.entrySet());
  24.         // 根据菜名进行排序，sortedDishesName拥有排序的entry，dishesName可以O(1)找到entry
  25.         Collections.sort(sortedDishesName, (Map.Entry<String, Integer> m1, Map.Entry<String, Integer> m2) -> {
  26.             return m1.getKey().compareTo(m2.getKey());
  27.         });
  28.         // 建立答案中第一行的菜名
  29.         List<String> firstRow = new ArrayList();
  30.         firstRow.add("Table");
  31.         for (Map.Entry<String, Integer> entry : sortedDishesName) {
  32.             firstRow.add(entry.getKey());
  33.         }
  34.         ans.add(firstRow);
  35.         for (Map.Entry<Integer, Map<String, Integer>> order : sortedTableOrder) {
  36.             List<String> temp = new ArrayList();
  37.             temp.add(String.valueOf(order.getKey()));
  38.             // 将点过的菜记录进dishesName
  39.             for (Map.Entry<String, Integer> dishes : order.getValue().entrySet()) {
  40.                 dishesName.put(dishes.getKey(), dishes.getValue());
  41.             }
  42.             // 生成添加进答案的行
  43.             for (Map.Entry<String, Integer> entry : sortedDishesName) {
  44.                 temp.add(String.valueOf(entry.getValue()));
  45.             }
  46.             // 清空dishesName中记录，便于做下一桌的记录
  47.             for (Map.Entry<String, Integer> entry : sortedDishesName) {
  48.                 entry.setValue(0);
  49.             }
  50.             ans.add(temp);
  51.         }
  52.         return ans;
  53.     }
  54. }

时间复杂度为O()，空间复杂度为O(n)