[Ежедневный алгоритм] Моделирование приложения структуры данных ｜ Месяц темы Python

задняя часть
[Ежедневный алгоритм] Моделирование приложения структуры данных ｜ Месяц темы Python

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

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

Это на LeetCode451. Сортировать по частоте символов, сложность в томсредний.

Тег: «моделирование», «сортировка сегментов», «хеш-таблица», «массив», «очередь с приоритетом (куча)»

Учитывая строку, отсортируйте символы в строке в порядке убывания частоты.

Пример 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

Пример 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

Пример 3:

输入:
"Aabb"

输出:

"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

Структуры данных + моделирование

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

Конкретные методы заключаются в следующем:

  1. Сначала используйте «хеш-таблицу» для подсчета частоты слов;
  2. Пройдитесь по хэш-таблице, которая подсчитывает частоту слов, и преобразуйте каждую пару ключ-значение в{字符,词频}хранятся в «очереди приоритетов (куче)». А логика сортировки "приоритетная очередь (куча)" определяется как:
    • если词频разные, согласно词频обратный порядок;
    • если词频то же, согласно字符字典序По возрастанию (поскольку в этом вопросе используется механизм Специального судьи, эта стратегия сортировки может быть скорректирована по желанию. Но обычно для того, чтобы гарантировать, что логика сортировки удовлетворяет «отношению общего порядка», это место может писать положительное и отрицательное, но теоретически , его нельзя писать, иначе нельзя каждый раз гарантировать результат сортировки один и тот же);
  3. Всплывающее окно из «очереди приоритетов (кучи)», чтобы построить ответ.

Код:

class Solution {
    class Node {
        char c; 
        int v;
        Node(char _c, int _v) {
            c = _c; v = _v;
        }
    }
    public String frequencySort(String s) {
        char[] cs = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : cs) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        PriorityQueue<Node> q = new PriorityQueue<>((a,b)->{
            if (b.v != a.v) return b.v - a.v;
            return a.c - b.c;
        });
        for (char c : map.keySet()) {
            q.add(new Node(c, map.get(c)));
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            Node poll = q.poll();
            int k = poll.v;
            while (k-- > 0) sb.append(poll.c);
        }
        return sb.toString();
    }
}

class Solution:
    def frequencySort(self, s: str) -> str:
        return "".join(char * repeats for char,repeats in sorted(Counter(s).items(), key=lambda x:-x[1]))
  • Временная сложность: пусть размер набора символов будетCC. Сложность использования «хеш-таблицы» для подсчета частоты слов составляетO(n)O(n); в худшем случае присутствуют все символы в наборе символов, не болееCCузлы для добавления в "приоритетную очередь (кучу)", сложностьO(Clog⁡C)O(C\log{C}); Построение ответа требует взятия элементов из «приоритетной очереди (кучи)» и их сращивания, сложностьO(n)O(n). Общая сложность составляетO(max⁡(n,Clog⁡C))O(\max(n, C\log{C}))
  • Сложность пространства:O(n)O(n)

Реализация массива + моделирование

Основная идея остается прежней, а структура данных, используемая в описанном выше процессе, заменяется массивом.

В частности, использование набора символов ASCII для128128биты, предварительно встроенные размером128128Массив, использующий идею «сортировки сегментов» для замены роли «хеш-таблицы» и «очереди с приоритетом (кучи)».

Код:

class Solution {   
    public String frequencySort(String s) {
        int[][] cnts = new int[128][2];
        char[] cs = s.toCharArray();
        for (int i = 0; i < 128; i++) cnts[i][0] = i;
        for (char c : cs) cnts[c][1]++;
        Arrays.sort(cnts, (a, b)->{
            if (a[1] != b[1]) return b[1] - a[1];
            return a[0] - b[0];
        });
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 128; i++) {
            char c = (char)cnts[i][0];
            int k = cnts[i][1];
            while (k-- > 0) sb.append(c);
        }
        return sb.toString();
    }
}

class Solution:
    def frequencySort(self, s: str) -> str:
        map = defaultdict(int)
        for c in s:
            map[c] += 1
        pq = []
        for k,v in map.items():
            heapq.heappush(pq, (-v, ord(k), k))
        ans = []
        while pq:
            repeats, _, char = heapq.heappop(pq)
            ans.append(char*-repeats)
        return "".join(ans)
  • Временная сложность: пусть размер набора символов будетCC. СложностьO(max⁡(n,Clog⁡C))O(\max(n, C\log{C}))
  • Сложность пространства:O(n+C+log⁡C)O(n + C + \log{C})

Наконец

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

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

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

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

Категории