[Ежедневный алгоритм] Сравнение двух реализаций хеш-таблицы и красно-черного дерева | Месяц темы Python

Эта статья участвует в "Месяце тем Python", подробнее см.Ссылка на мероприятие

Описание темы

Это на LeetCode1418. Стол для отображения заказов, трудность в томсредний.

Тег : "структура данных", "хеш-таблица", "красно-черное дерево"

Вам дан массив заказов, представляющий заказы, выполненные клиентами в ресторане, если быть точным,orders[i]=[customerNamei,tableNumberi,foodItemi] ,вcustomerNamei имя клиента,tableNumberi это номер стола клиента, иfoodItemi название блюда, заказанного покупателем.

Пожалуйста, вернитесь к столику с обслуживанием по меню в ресторане. В этой таблице первая строка в таблице — название, первый столбец — номер стола «Стол», а каждый последующий столбец — название блюда в алфавитном порядке. Элементы в следующей строке представляют соответствующее количество блюд, заказанных за каждым столом.Первая колонка должна быть заполнена соответствующим номером стола, за которым следует количество заказа.

Примечание. Имена клиентов не являются частью формы отображения заказа. Кроме того, строки данных в таблице должны быть отсортированы в порядке возрастания по номеру таблицы.

Пример 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.

---

Фундаментальный анализ

Это проблема моделирования, которая рассматривает «приложение структуры данных» и «простой дизайн».

Мы можем сделать вывод о формате хранения структуры данных на основе конечного «результата».

Окончательный «результат» состоит из двух частей:

1. title: Зависит от"Таблица" + сортировка дедуплицированных блюдсочинение
2. Содержание: поНомер таблицы + количество для каждого элементасочинение

Исходя из этого, нетрудно спроектировать использованиеSetместо храненияtitleсвязанный контент, используяMapХраните соответствующую часть контента.

дедупликацияMapчастьKeyэто номер стола, и чтобы быстро проиндексировать текущий номер стола «количество определенного блюда», необходимо установить еще один слойMap. То есть окончательный формат хранения桌号 : {餐品 : 个数}.

---

HashSet & HashMap

При базовом анализе мы можем использовать самые обычныеHashSetиHashMapреализовать.

так какHashSetоснован наHashMap,иHashMapБазовая реализация структуры данныххеш-таблица, поэтому нам нужно вручную отсортировать порядок при построении ответа.

Java-код:

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;
    }
}

Код 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Основные операции$O(1)$. Сложность предварительной обработки всех заказов составляет$O(n)$; Количество таблиц после дедупликации равно$r$, количество приемов пищи$c$, сложность сортировки двух$O(r\log{r})$и$O(c\log{c})$; Сложность построения ответа$O(r * c)$; конечная сложность$O(\max(n, r\log{r}, c\log{c}, r * c))$
• Сложность пространства:$O(r + c + r * c)$

---

TreeSet & TreeMap

иHashSetиHashMapотношения похожи,TreeSetоснован наTreeMapпонял, иTreeMapБазовая реализация структуры данныхкрасно-черное дерево.

Благодаря дизайну Java «интерфейсно-ориентированное программирование (IOP)», мы можем легко преобразоватьHashSetзаменитьTreeSet,будетHashMapзаменитьTreeMap, и удалите код, связанный с ручной сортировкой, чтобы получить наше решение два.

использоватьTreeMapСопоставление по умолчанию (числовое возрастание, нечисловое лексикографическое возрастание) для упрощения нашей реализации.

Однако следует отметить, что использованиеTreeMapФункция внутреннего упорядочения операции корректировки может происходить в каждой операции вставки, и решение состоит в использованииCollections.sortВыполнить однократную сортировку для нестандартных классовCollections.sortоснован наArrays.sortВ случае ее реализации итоговая схема сортировки будет всесторонне определяться такими факторами, как «размер массива» и «примерно ли упорядочен сам массив». В случае полностью случайных данных эффективность выполнения во многом лучше, чемTreeMapнесколько корректировок , но сложность обоих одинакова$O(n\log{n})$.

Поэтому в случае «офлайн», когда все данные предоставляются заранее, на самом деле более рекомендуется использовать решение 1.

Java-код:

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;
    }
}

Код Python3:

from sortedcontainers import SortedSet, SortedDict

class 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Основные операции$O(log{k})$. Сложность предварительной обработки всех заказов составляет$O(n\log{n})$; Количество таблиц после дедупликации равно$r$, количество приемов пищи$c$, сложность построения ответа$O(r\log{r} * c\log{c})$; конечная сложность$O(\max(n\log{n}, r\log{r} * c\log{c}))$
• Сложность пространства:$O(r + c + r * c)$

---

Наконец

Это первая статья из нашей серии «Пройдитесь по LeetCode».No.1418Серия стартует 01.01.2021.На момент старта на LeetCode 1916 вопросов, некоторые из которых заблокированы.Сначала закончим все вопросы без замков.

В этой серии статей, помимо объяснения идей решения проблем, будет дан максимально лаконичный код. Если речь идет об общих решениях, также будут предоставлены соответствующие шаблоны кода.

Чтобы облегчить студентам отладку и отправку кода на компьютере, я создал соответствующие склады:GitHub.com/sharing кислый….

В адресе склада вы можете увидеть ссылку на решение серии статей, соответствующий код серии статей, ссылку на исходный вопрос LeetCode и другие предпочтительные решения.