1418-点菜展示表

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

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

方法一：哈希表

我们首先分析题目需要我们做些什么：

  • 我们需要将订单信息进行汇总，存放在一张数据表中作为答案返回；
  • 数据表的第一行包含了所有的餐品名称，并且需要按照餐品名称的字典序排序，因此我们需要遍历订单信息，获取所有的餐品名称并对它们进行排序；
  • 数据表的第一列包含了所有的餐桌桌号，并且需要按照桌号排序，因此我们需要遍历订单信息，获取所有的桌号并对它们进行排序；
  • 数据表中间包含的信息为「某一桌下单的某一道菜的数量」。

我们可以使用两个哈希表来保存订单中的数据：

  • 哈希表 nameSet 保存所有的餐品名称；
  • 哈希表 foodsCnt 保存桌号及该桌点餐数量，点餐数量也用一个哈希表保存。

遍历订单并保存信息后，从 nameSet 中提取餐品名称，并按字母顺序排列；从 foodsCnt 中提取桌号，并按桌号升序排列。然后将餐品名称和桌号分别填入点菜展示表的第一行和第一列。对于表中的餐品数量，我们逐行填入，对于每一行，我们遍历餐品名称，在 foodsCnt 中查找对应的点餐数量，然后填入表格中对应位置。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>> &orders) {
        // 从订单中获取餐品名称和桌号，统计每桌点餐数量
        unordered_set<string> nameSet;
        unordered_map<int, unordered_map<string, int>> foodsCnt;
        for (auto &order : orders) {
            nameSet.insert(order[2]);
            int id = stoi(order[1]);
            ++foodsCnt[id][order[2]];
        }

        // 提取餐品名称，并按字母顺序排列
        int n = nameSet.size();
        vector<string> names;
        for (auto &name : nameSet) {
            names.push_back(name);
        }
        sort(names.begin(), names.end());

        // 提取桌号，并按餐桌桌号升序排列
        int m = foodsCnt.size();
        vector<int> ids;
        for (auto &[id, _] : foodsCnt) {
            ids.push_back(id);
        }
        sort(ids.begin(), ids.end());

        // 填写点菜展示表
        vector<vector<string>> table(m + 1, vector<string>(n + 1));
        table[0][0] = "Table";
        copy(names.begin(), names.end(), table[0].begin() + 1);
        for (int i = 0; i < m; ++i) {
            int id = ids[i];
            auto &cnt = foodsCnt[id];
            table[i + 1][0] = to_string(id);
            for (int j = 0; j < n; ++j) {
                table[i + 1][j + 1] = to_string(cnt[names[j]]);
            }
        }
        return table;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public List<List<String>> displayTable(List<List<String>> orders) {
        // 从订单中获取餐品名称和桌号，统计每桌点餐数量
        Set<String> nameSet = new HashSet<String>();
        Map<Integer, Map<String, Integer>> foodsCnt = new HashMap<Integer, Map<String, Integer>>();
        for (List<String> order : orders) {
            nameSet.add(order.get(2));
            int id = Integer.parseInt(order.get(1));
            Map<String, Integer> map = foodsCnt.getOrDefault(id, new HashMap<String, Integer>());
            map.put(order.get(2), map.getOrDefault(order.get(2), 0) + 1);
            foodsCnt.put(id, map);
        }

        // 提取餐品名称，并按字母顺序排列
        int n = nameSet.size();
        List<String> names = new ArrayList<String>();
        for (String name : nameSet) {
            names.add(name);
        }
        Collections.sort(names);

        // 提取桌号，并按餐桌桌号升序排列
        int m = foodsCnt.size();
        List<Integer> ids = new ArrayList<Integer>();
        for (int id : foodsCnt.keySet()) {
            ids.add(id);
        }
        Collections.sort(ids);

        // 填写点菜展示表
        List<List<String>> table = new ArrayList<List<String>>();
        List<String> header = new ArrayList<String>();
        header.add("Table");
        for (String name : names) {
            header.add(name);
        }
        table.add(header);
        for (int i = 0; i < m; ++i) {
            int id = ids.get(i);
            Map<String, Integer> cnt = foodsCnt.get(id);
            List<String> row = new ArrayList<String>();
            row.add(Integer.toString(id));
            for (int j = 0; j < n; ++j) {
                row.add(Integer.toString(cnt.getOrDefault(names.get(j), 0)));
            }
            table.add(row);
        }
        return table;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class Solution {
    public IList<IList<string>> DisplayTable(IList<IList<string>> orders) {
        // 从订单中获取餐品名称和桌号，统计每桌点餐数量
        ISet<string> nameSet = new HashSet<string>();
        Dictionary<int, Dictionary<string, int>> foodsCnt = new Dictionary<int, Dictionary<string, int>>();
        foreach (IList<string> order in orders) {
            nameSet.Add(order[2]);
            int id = int.Parse(order[1]);
            Dictionary<string, int> dictionary = foodsCnt.ContainsKey(id) ? foodsCnt[id] : new Dictionary<string, int>();
            if (dictionary.ContainsKey(order[2])) {
                ++dictionary[order[2]];
            } else {
                dictionary.Add(order[2], 1);
            }
            if (!foodsCnt.ContainsKey(id)) {
                foodsCnt.Add(id, dictionary);
            }
        }

        // 提取餐品名称，并按字母顺序排列
        int n = nameSet.Count;
        List<string> names = new List<string>();
        foreach (string name in nameSet) {
            names.Add(name);
        }
        names.Sort((a, b) => string.CompareOrdinal(a, b));

        // 提取桌号，并按餐桌桌号升序排列
        int m = foodsCnt.Count;
        List<int> ids = new List<int>();
        foreach (int id in foodsCnt.Keys) {
            ids.Add(id);
        }
        ids.Sort();

        // 填写点菜展示表
        IList<IList<string>> table = new List<IList<string>>();
        IList<string> header = new List<string>();
        header.Add("Table");
        foreach (string name in names) {
            header.Add(name);
        }
        table.Add(header);
        for (int i = 0; i < m; ++i) {
            int id = ids[i];
            Dictionary<string, int> cnt = foodsCnt[id];
            IList<string> row = new List<string>();
            row.Add(id.ToString());
            for (int j = 0; j < n; ++j) {
                int val = cnt.ContainsKey(names[j]) ? cnt[names[j]] : 0;
                row.Add(val.ToString());
            }
            table.Add(row);
        }
        return table;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func displayTable(orders [][]string) [][]string {
    // 从订单中获取餐品名称和桌号，统计每桌点餐数量
    nameSet := map[string]struct{}{}
    foodsCnt := map[int]map[string]int{}
    for _, order := range orders {
        id, _ := strconv.Atoi(order[1])
        food := order[2]
        nameSet[food] = struct{}{}
        if foodsCnt[id] == nil {
            foodsCnt[id] = map[string]int{}
        }
        foodsCnt[id][food]++
    }

    // 提取餐品名称，并按字母顺序排列
    n := len(nameSet)
    names := make([]string, 0, n)
    for name := range nameSet {
        names = append(names, name)
    }
    sort.Strings(names)

    // 提取桌号，并按餐桌桌号升序排列
    m := len(foodsCnt)
    ids := make([]int, 0, m)
    for id := range foodsCnt {
        ids = append(ids, id)
    }
    sort.Ints(ids)

    // 填写点菜展示表
    table := make([][]string, m+1)
    table[0] = make([]string, 1, n+1)
    table[0][0] = "Table"
    table[0] = append(table[0], names...)
    for i, id := range ids {
        cnt := foodsCnt[id]
        table[i+1] = make([]string, n+1)
        table[i+1][0] = strconv.Itoa(id)
        for j, name := range names {
            table[i+1][j+1] = strconv.Itoa(cnt[name])
        }
    }
    return table
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
var displayTable = function(orders) {
    // 从订单中获取餐品名称和桌号，统计每桌点餐数量
    const nameSet = new Set();
    const foodsCnt = new Map();
    for (const order of orders) {
        nameSet.add(order[2]);
        const id = parseInt(order[1]);
        const map = foodsCnt.get(id) || new Map();
        map.set(order[2], (map.get(order[2]) || 0) + 1);
        foodsCnt.set(id, map);
    }

    // 提取餐品名称，并按字母顺序排列
    const n = nameSet.size;
    const names = [];
    for (const name of nameSet) {
        names.push(name);
    }
    names.sort();

    // 提取桌号，并按餐桌桌号升序排列
    const m = foodsCnt.size;
    const ids = [];
    for (const id of foodsCnt.keys()) {
        ids.push(id);
    }
    ids.sort((a, b) => a - b);

    // 填写点菜展示表
    const table = [];
    const header = [];
    header.push("Table");
    for (const name of names) {
        header.push(name);
    }
    table.push(header);
    for (let i = 0; i < m; ++i) {
        const id = ids[i];
        const cnt = foodsCnt.get(id);
        const row = [];
        row.push(id.toString());
        for (let j = 0; j < n; ++j) {
            row.push((cnt.get(names[j]) || 0).toString());
        }
        table.push(row);
    }
    return table;
};

复杂度分析

为了便于进行复杂度分析，我们将所有字符串长度均视作常数。

  • 时间复杂度：O(T + N\log N + M\log M + MN)。其中 T 是数组 orders 的长度，N 是数据表的列数（即餐品的数量），M 是数据表的行数（即餐桌的数量）。时间复杂度由以下几个部分组成：
    • 遍历订单并保存信息的时间复杂度为 O(T)；
    • 对餐品名称和餐桌编号分别进行排序，时间复杂度分别为 O(N \log N) 和 O(M \log M)；
    • 将数据逐行填入表格，时间复杂度为 O(MN)。
  • 空间复杂度：O(T + N + M)。注意这里只计算额外的空间复杂度，不计入存放最终数据表（即答案）需要的空间。
 Comments
On this page
1418-点菜展示表