class Solution { public: string frequencySort(string s) { string result = ""; priority_queue<pair<int, char>> q; unordered_map<char, int> freq; for (auto ch : s) { freq[ch]++; } for (auto ch : s) { q.push({freq[ch], ch}); } while (!q.empty()) { result += q.top().second; q.pop(); } return result; } };

Ой, priority que

только это всё равно N * log N

Память N

Попробуй. А я пока пытаюсь понять решение

Блин, как вы все это успеваете, я три дня пытался это дерево обойти :)

джуниором себя ощущаю 🙂

class Solution { public: string frequencySort(string s) { string result = ""; priority_queue<pair<int, char>> q; unordered_map<char, int> freq; for (auto ch : s) { freq[ch]++; } for (auto ch : s) { q.push({freq[ch], ch}); } while (!q.empty()) { result += q.top().second; q.pop(); } return result; } };

Как я понял, или O(N logN) O(1)

Аккуратно вышло)

или точнее n*sqrt(n)

Worst case: Linear in the container size.

Типо если Хэш функция “закончитя”

то есть?

Худший случай, если хэш функция “поймает” все элементы который в сете

https://pastebin.com/VSGai560

https://pastebin.com/VSGai560

Шило на мыло

@vitkarpov было бы не плохо, если бы меня поправили

Всё же склоняюсь, что в первом варианте было n^2 в худшем случае

Из-за set.erase?

Как Удаление Хэш элемента может быть медленнее O(1)?

Это же tree под капотом

https://pastebin.com/VSGai560

Думаю может можно без памяти обойтись 🤣

Монстрик побежден 🤣