Medium

题目描述

给你一个数组 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"]]

示例 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"]]

示例 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. 数据收集：遍历所有订单，统计每张桌子上每种食物的数量
  2. 排序处理：桌号按数字升序，食物名按字母升序
  3. 表格构建：根据统计结果构建最终的显示表

具体步骤：

  • 使用哈希表统计每个(桌号, 食物)对的频次
  • 使用集合收集所有唯一的桌号和食物名
  • 对桌号和食物名分别排序
  • 构建表头：第一列为"Table"，后续列为排序后的食物名
  • 构建数据行：每行对应一个桌号，各列为该桌号对应食物的订购数量

时间复杂度分析：

  • 统计订单：O(n)，其中n是订单数量
  • 排序桌号：O(t log t)，其中t是桌子数量
  • 排序食物：O(f log f)，其中f是食物种类数
  • 构建结果：O(t × f)
  • 总体：O(n + t log t + f log f + t × f)

这种方法直观且高效，适合处理餐厅订单统计的实际场景。

代码实现

class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        map<int, map<string, int>> table_orders;
        set<string> foods;
        
        // 统计每桌每种食物的数量
        for (auto& order : orders) {
            int table = stoi(order[1]);
            string food = order[2];
            table_orders[table][food]++;
            foods.insert(food);
        }
        
        vector<vector<string>> result;
        
        // 构建表头
        vector<string> header = {"Table"};
        for (const string& food : foods) {
            header.push_back(food);
        }
        result.push_back(header);
        
        // 构建数据行
        for (auto& [table, food_counts] : table_orders) {
            vector<string> row = {to_string(table)};
            for (const string& food : foods) {
                row.push_back(to_string(food_counts[food]));
            }
            result.push_back(row);
        }
        
        return result;
    }
};

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        from collections import defaultdict
        
        # 统计每桌每种食物的数量
        table_orders = defaultdict(lambda: defaultdict(int))
        foods = set()
        
        for customer, table, food in orders:
            table_orders[int(table)][food] += 1
            foods.add(food)
        
        # 排序
        sorted_tables = sorted(table_orders.keys())
        sorted_foods = sorted(foods)
        
        result = []
        
        # 构建表头
        header = ["Table"] + sorted_foods
        result.append(header)
        
        # 构建数据行
        for table in sorted_tables:
            row = [str(table)]
            for food in sorted_foods:
                row.append(str(table_orders[table][food]))
            result.append(row)
        
        return result

public class Solution {
    public IList<IList<string>> DisplayTable(IList<IList<string>> orders) {
        var tableOrders = new SortedDictionary<int, Dictionary<string, int>>();
        var foods = new SortedSet<string>();
        
        // 统计每桌每种食物的数量
        foreach (var order in orders) {
            int table = int.Parse(order[1]);
            string food = order[2];
            
            if (!tableOrders.ContainsKey(table)) {
                tableOrders[table] = new Dictionary<string, int>();
            }
            
            if (!tableOrders[table].ContainsKey(food)) {
                tableOrders[table][food] = 0;
            }
            
            tableOrders[table][food]++;
            foods.Add(food);
        }
        
        var result = new List<IList<string>>();
        
        // 构建表头
        var header = new List<string> { "Table" };
        header.AddRange(foods);
        result.Add(header);
        
        // 构建数据行
        foreach (var table in tableOrders.Keys) {
            var row = new List<string> { table.ToString() };
            foreach (var food in foods) {
                int count = tableOrders[table].ContainsKey(food) ? tableOrders[table][food] : 0;
                row.Add(count.ToString());
            }
            result.Add(row);
        }
        
        return result;
    }
}

var displayTable = function(orders) {
    const tableOrders = new Map();
    const foods = new Set();
    
    // 统计每桌每种食物的数量
    for (const [customer, table, food] of orders) {
        const tableNum = parseInt(table);
        
        if (!tableOrders.has(tableNum)) {
            tableOrders.set(tableNum, new Map());
        }
        
        const foodMap = tableOrders.get(tableNum);
        foodMap.set(food, (foodMap.get(food) || 0) + 1);
        foods.add(food);
    }
    
    // 排序
    const sortedTables = Array.from(tableOrders.keys()).sort((a, b) => a - b);
    const sortedFoods = Array.from(foods).sort();
    
    const result = [];
    
    // 构建表头
    const header = ["Table", ...sortedFoods];
    result.push(header);
    
    // 构建数据行
    for (const table of sortedTables) {
        const row = [table.toString()];
        const foodMap = tableOrders.get(table);
        
        for (const food of sortedFoods) {
            row.push((foodMap.get(food) || 0).toString());
        }
        
        result.push(row);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + t log t + f log f + t × f)，其中 n 是订单数量，t 是桌子数量，f 是食物种类数
空间复杂度O(t × f)，用于存储每张桌子每种食物的统计信息