Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 30
×

Вирішуємо задачу з Leetcode: Top K Frequent Elements

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Привіт! Мене звати Данило Толмачов, я Full-Stack розробник і Team Lead у Techstack. Думаю, багато хто з нас розв’язує задачі на Leetcode: для розваги, розвитку або щоб потрапити на роботу в FAANG. Завдань різної складності на Leetcode дуже багато. У цій статті я покажу декілька варіантів розв’язання задачі Top K Frequent Elements.

Стаття буде корисною тим, хто вивчає алгоритми, розвиває логічне мислення або готується до співбесіди на позицію будь-якого рівня.

У чому суть задачі

Top K Frequent Elements — це універсальна базова алгоритмічна задача, яка відзначена на Leetcode середнім рівнем складності. Гадаю, вона буде корисною багатьом, оскільки майже всі працюють з масивами і знають, що таке хешмеп. Подивімось докладніше, у чому її суть.

Задача: 347. Top K Frequent Elements

Given an integer array nums and an integer k, return themost frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

  • 1 <= nums.length <= 10⁵
  • -10⁴ <= nums[i] <= 10⁴
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than Θ(n log(n)), where n is the array’s size.

Підхід до розв’язання

Перш ніж переходити до розв’язання, розберемось, як логічно підходити до роботи з такими завданнями, з чого починати і як діяти:

Крок 1: Розберіться, яке перед вами завдання. Для цього починаємо з читання вимог. Що в нас є з умов:

1) integer array nums на вході та integer k — звичайне, недробове, число. Це найчастіше зустрічаються елементи на вході.

2) Відповідь може бути дана в будь-якому порядку.

Крок 2: Вивчіть приклади. Вони допоможуть зрозуміти, що конкретно потрібно зробити. У цій задачі прикладів два:

Example 1:

Input: nums = [1,1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

З прикладів та умови стає зрозуміло, що у нас є масив nums, і нам потрібно знайти два найпопулярніші елементи в ньому.

Крок 3: Не пропускайте обмеження задачі. Це часта помилка, яка призводить або до неправильних, або до неоптимальних рішень. Конкретно в цьому завданні у нас є обмеження на розмір і значення вхідних та вихідних даних, а також розмір масиву і кількість необхідних елементів:

1 <= nums.length <= 10⁵

-10⁴ <= nums[i] <= 10⁴

k is in the range [1, the number of unique elements in the array].

It is guaranteed that the answer is unique.

Звідси робимо висновок, що значення елементів можуть бути як від’ємними, так і додатними, а також — що відповідь завжди унікальна.

Як мислити, щоб розв’язати цю задачу

Перш ніж перекладати розв’язання мовою програмування, потрібно зрозуміти, як мислити загалом. Краще один раз добре подумати, ніж багато разів рефакторити і переписувати код. Тому раджу спочатку виробити алгоритм, а потім братися за написання коду.

Не забувайте, що мова — це просто інструмент, який не вирішує за вас, а допомагає донести комп’ютеру ваше рішення.

Як можна діяти в цьому випадку? Починаємо розбирати алгоритм для першого прикладу:

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Запитайте себе, які елементи зустрічаються найчастіше. Відповідь: 1 і 2. Як ми до цього прийшли? Розкладаємо своє мислення на атомарні операції, які можна перекласти мовою програмування.

Уявімо, що в нас є блокнот, куди ми записуємо кожен елемент, проходячи масивом. Звертаємо увагу, скільки разів кожен із них зустрічався. Наприклад, дивимося на перший елемент. Це цифра один — записуємо, що одиниця зустрілася один раз. Переходимо до другого елемента: знову одиниця — збільшуємо лічильник цифри один та ін. І тоді наша таблиця з нотатками має такий фінальний вигляд: одиниці трапляються тричі, двійки — двічі, трійки — один раз.

За умовами з цього списку потрібно вибрати топ n-елементів (ті, які зустрічаються найчастіше). У цьому випадку це k, і k=2.

Потрібно розуміти, що як приклад подано найпростіші речі. Умови, які даватимуться потім, не обов’язково з’являтимуться в тому ж порядку і кількості. В іншому масиві тих самих трійок могло бути більше, а двійок менше, або цей масив міг би розширитися і всіх елементів стало б більше. Тоді ми б напевно не знали, що саме потрібно брати як топ n-елементів. Звідси з’являється потреба відсортувати масив.

Закінчивши розбиратися з алгоритмом, переходимо до перетворення його на код. Готовий алгоритм можна написати будь-якою мовою. І навіть усередині однієї мови існує безліч варіацій кінцевої реалізації. Я буду використовувати JavaScript, і покажу два варіанти рішення, розуміючи, що вони не є єдиними.

Розв’язання 1

Перш ніж переходити безпосередньо до розв’язання, хочу зазначити, що воно навмисно було розраховане без урахування follow up — тієї частини завдання, яку часто не беруть до уваги. Без неї ми зможемо спочатку отримати рішення, що працює, а потім перейдемо до оптимізації, враховуючи follow up.

Отже, перше розв’язання:

const map = {}
nums.forEach(n => {
  map[n] = map[n] ? ++map[n] : 1
})

const keysSorted = Object.keys(map).sort((a,b) => {return map[b]-map[a]})

return keysSorted.slice(0, k).map(key => parseInt(key))

Тепер давайте покроково розбиратися, як працює це рішення.

1. Наповнюємо map

В основі розв’язання лежить змінна map, яка є об’єктом. Після створення map ми запускаємо цикл по масиву вхідних цифр nums. Так ми починаємо підрахунок кількості цифр, що зустрічаються. Ім’я кожної властивості об’єкта — це цифра, а значення цієї властивості — кількість разів, скільки ця цифра зустрілася нам на шляху. Усе це ми присвоюємо в map.

2. Переходимо до сортування ключів (keysSorted)

Наступним етапом оголошуємо змінну keysSorted. За підсумком проходження масивом ми повинні отримати всі ключі об’єкта map, які в ньому записані. Після чого починаємо сортування ключів від більшого до меншого залежно від їхніх значень.

Зрештою отримуємо відсортований масив keysSorted, який міститиме імена всіх ключів, відсортованих за частотою їхньої появи в оригінальному масиві nums: [«1», «2», «3»].

Є безліч хороших сортувань, але оптимальні з них у середньому показують результат за time complexity: Θ(n log(n)). Це лінійно-логорифмічна залежність.

3. Проводимо слайс масиву

На наступному етапі потрібно зробити слайс масиву і відрізати k-елементи, а потім привести їх до parseInt. Це пов’язано з тим, що всі ключі в JS обробляються як рядки, а нам потрібно привести результат до цифр. Так у нас запускається другий цикл за k-елементами, які були відрізані.

4. Оцінюємо складність цього алгоритму

Для цього попрацюємо з Big O notation, який добре допомагає з оцінкою складності, зокрема, time complexity та space complexity. Big O notation вказує на те, що якщо в алгоритмі є цикл по всіх елементах вхідного масиву, то це пряма залежність від об’єму вхідних даних і складність O(n). Відповідно, хоча б один раз ми точно відвідаємо цей елемент, а O дорівнюватиме O(n). Звідси випливає, що n-раз ми точно пройдемося по кожному з елементів.

Перший цикл: O(n)

Другий цикл (за сортуванням): Θ(n log(n))

Третій цикл: O(k)

Далі залучаємо математику й оцінку складності розв’язання:

O(n) + O(n log n) + O(k) => O(n log n)

Що цікавого в розв’язанні 1

У ньому n — це довжина вхідних даних. У нашому випадку довжина nums — шість, але кількість ключів, які ми сортуємо, — три, тому що це унікальні цифри.

Це дуже простий приклад. Ми повинні розуміти, що в гіршому варіанті можна отримати цілий масив унікальних чисел. Відповідно, розмір map буде набагато більшим.

Що за результатами

Перший сабмішн виконано за 85 мс і 43 мб пам’яті, а це на 98% краще за інші рішення.

Розв’язання 2

Здавалося б, усе вже вийшло чудово, але є одна важлива деталь — під час першого розв’язання ми не врахували follow up:

«Your algorithm’s time complexity must be better than Θ(n log(n)), where n is the array’s size».

Розв’язання, яке ми отримали, не відповідає follow up, тому що базується на Θ(n log(n)), тоді як воно має бути кращим. Відповідно, виникає питання, як зробити розв’язання кращим, ніж Θ(n log(n))?

Оцінка складності попереднього розв’язання показала, що його слабким місцем було сортування. Отже, у новому розв’язанні його потрібно переглянути. Ми не будемо відмовлятися від підходу зі створенням map, але змінимо підхід до сортування цифр.

Яку логіку тут можна використовувати? Пропоную виходити з того, що у нас є масив із шести елементів. Зробимо додатковий «список» рівним довжині оригінального масиву (nums): тобто, виходячи з першого прикладу, nums.length = 6. Відповідно, список частот міститиме цифри від одного до 6.

У цьому підході індекси відповідатимуть за частоту появи цифр, а значення, які зберігаються за цими індексами — це цифри. Виходячи з цього, заповнимо «список» частот: ми бачимо одиницю і бачимо, що її частота 3 — ставимо її в трійку; бачимо двійку — ставимо в двійку; бачимо трійку — ставимо в одиницю.

Принцип роботи тут — від зворотного: коли потрібно видавати топ k-елементів, ми будемо звертати увагу на частоту.

Після заповнення «списку» з частотами, справа залишилася за малим — потрібно дістати з нього k найпопулярніших елементів. Проходимося масивом частот у зворотному порядку і дістаємо значення з нього, зберігаючи їх у наш результуючий масив доти, доки розмір фінального масиву не дорівнюватиме k. Тепер наш result aray = k. На цьому можна закінчувати вправу.

Переносимо цю логіку в код і отримуємо:

const map = {}
nums.forEach(n => {
  map[n] = map[n] ? ++map[n] : 1
})

let result = []
const frequencies = []
for (const [digit, appearance] of Object.entries(map)) {
  if (frequencies[appearance]) {
    frequencies[appearance].push(parseInt(digit))
  } else {
    frequencies[appearance] = [parseInt(digit)]
  }
}

for(let i = nums.length; result.length < k; i--) {
  result = result.concat(frequencies[i] || [])
}

return result

Перша частина із заповненням об’єкта map не змінилася, переносимо з минулого рішення.

Новий підхід замість сортування, як було раніше, створюємо масив frequencies, і, проходячи по об’єкту map в циклі, заповнюємо частоти відповідними значеннями.

Тепер нам потрібно забрати всі елементи з frequencies array. Для цього знову перевіряємо масив: переходимо в 6 — нічого немає, йдемо далі. Ініціалізуємо змінну індексів з максимальним розміром nums. Потім дістаємо цифри з частотного масиву, доти, доки їх не буде k штук. Ми рухаємося у зворотному порядку, щоб забрати ті, що зустрічаються найчастіше. У гіршому випадку, якщо всі діджити унікальні і k = length array, нам потрібно буде пройти по всьому frequence array.

За допомогою такого розв’язання ми отримуємо результат за 100 мс з використанням 48 мб пам’яті.

Якщо вірити умовам задачі, ми повинні були отримати ефективніше рішення. Звідси запитання:

Якщо складність цього алгоритму дорівнює o(n), а попередня складність Θ(n log(n)), то чому o(n), що мала б бути простішою і швидшою за перший, виявилася повільнішою?

Можливо, останній код неоптимальний і виконує надлишкові операції. Що думаєте з цього приводу? Обговорюймо в коментарях.

Що маємо в підсумку

Наостанок хочу тільки ще раз нагадати, що будь-яке завдання часто має кілька варіантів розв’язання: більш/ менш складні, більш/ менш ефективні. Важливо те, яку мету ви переслідуєте в пошуку рішення. Тому я б радив починати з уточнення цілей.

Запитайте інтерв’юера на співбесіді або клієнта під час виконання завдань, чого вам потрібно досягти в підсумку. Так ви зможете уникнути надмірного ускладнення або, навпаки, спрощення. Оверінжиніринг нікого не вразить, якщо досягти тієї самої мети можна простішим способом.

Друге, що хочеться ще раз проговорити, — уважно читайте реквайерменти. Найчастіше в них уже відразу прописано все, що потрібно для вашого рішення. Прочитайте все, що вам дано, і враховуйте це при побудові рішення.

І останнє — не недооцінюйте алгоритми. Вони допомагають підтримувати жвавість розуму і помічати патерни, які допоможуть у розв’язанні складніших завдань. Алгоритми лежать в основі будь-якої програми. Що краще ви розумітимете основи, то кращим буде ваш код.

👍ПодобаєтьсяСподобалось12
До обраногоВ обраному6
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Решение на питоне

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [num for num, freq in Counter(nums).most_common(k)]

Тест на скорость:

    nums = [1, 1, 2, 3, 3, 3, 4, 4]
    for i in (1000, 10_000, 100_000, 1_000_000, 10_000_000):
        arr = nums * i
        start = perf_counter()
        top_k = [num for num, freq in Counter(arr).most_common(10)]
        stop = perf_counter()
        print(f"N = {i}, time = {stop - start}, top = {top_k}")

Результаты замеров:

N = 1000, time = 0.0006012999801896513, top = [3, 1, 4, 2]
N = 10000, time = 0.005936999979894608, top = [3, 1, 4, 2]
N = 100000, time = 0.06925569998566061, top = [3, 1, 4, 2]
N = 1000000, time = 0.6199024000088684, top = [3, 1, 4, 2]
N = 10000000, time = 4.72007979999762,

социальными сетями прибило как выглядит реальный литкод код

www.reddit.com/...​_not_working_as_expected

ЗЫ: добавлю сам код чисто для истории

#include <vector>
#include <stack>
#include <utility>
#include <string>
#include <iostream>
#include <unordered_set>

using namespace std;

struct Hash
{
    std::size_t operator()(const std::vector<int> &vec) const
    {
        std::size_t seed = vec.size();
        for (auto x : vec)
        {
            seed ^= x + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }
        return seed;
    }
};

bool canReachPacific(const vector<vector<int>> &heights, unordered_set<vector<int>, Hash> &visited, int startRow, int startCol);
bool canReachAtlantic(const vector<vector<int>> &heights, unordered_set<vector<int>, Hash> &visited, int startRow, int startCol);
void displaySet(unordered_set<vector<int>, Hash> set);

vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights)
{
    vector<vector<int>> result;
    for (int row = 0; row < heights.size(); row++)
    {
        for (int col = 0; col < heights[0].size(); col++)
        {
            unordered_set<vector<int>, Hash> visited1;
            unordered_set<vector<int>, Hash> visited2;
            bool reachedPacific = canReachPacific(heights, visited1, row, col);
            // displaySet(visited1);
            bool reachedAtlantic = canReachAtlantic(heights, visited2, row, col);
            displaySet(visited2);
            std::cout << "row = " << row << ", col = " << col << std::endl;
            std::cout << "canReachPacific = " << (reachedPacific ? "true" : "false") << std::endl;
            std::cout << "canReachAtlantic = " << (reachedAtlantic ? "true" : "false") << std::endl;
            std::cout << std::endl;
            if (reachedPacific && reachedAtlantic)
            {
                result.push_back({row, col});
            }
        }
    }
    return result;
}

bool canReachPacific(const vector<vector<int>> &heights, unordered_set<vector<int>, Hash> &visited, int startRow, int startCol)
{
    bool result = false;

    visited.insert({startRow, startCol});
    vector<vector<int>> nextPositions = {
        {startRow - 1, startCol},
        {startRow + 1, startCol},
        {startRow, startCol + 1},
        {startRow, startCol - 1}};

    for (vector<int> position : nextPositions)
    {
        if ((0 <= position[0] && position[0] < heights.size()) && (0 <= position[1] && position[1] < heights[0].size()))
        {
            if (heights[startRow][startCol] >= heights[position[0]][position[1]])
            {
                if (visited.find(position) == visited.end())
                {
                    result = result || canReachPacific(heights, visited, position[0], position[1]);
                    if (result)
                    {
                        break;
                    }
                }
            }
        }
        else
        {
            if (position[0] < 0 || position[1] < 0)
            {
                result = true;
                break;
            }
            else
            {
                result = false;
            }
        }
    }

    return result;
}

bool canReachAtlantic(const vector<vector<int>> &heights, unordered_set<vector<int>, Hash> &visited, int startRow, int startCol)
{
    bool result = false;

    visited.insert({startRow, startCol});
    vector<vector<int>> nextPositions = {
        {startRow - 1, startCol},
        {startRow + 1, startCol},
        {startRow, startCol + 1},
        {startRow, startCol - 1}};

    for (vector<int> position : nextPositions)
    {
        if ((0 <= position[0] && position[0] < heights.size()) && (0 <= position[1] && position[1] < heights[0].size()))
        {
            if (heights[startRow][startCol] >= heights[position[0]][position[1]])
            {
                if (visited.find(position) == visited.end())
                {
                    result = result || canReachAtlantic(heights, visited, position[0], position[1]);
                    if (result)
                    {
                        break;
                    }
                }
            }
        }
        else
        {
// THIS LINE BELOW IS THE PROBLEM
            if (((position[0]) >= (heights.size())) || ((position[1]) >= (heights[0].size())))
            {   
                result = result || true;
                break;
            }
            else
            {
                result = result || false;
            }
        }
    }

    return result;
}

void displaySet(unordered_set<vector<int>, Hash> set)
{
    for (auto position : set)
    {
        std::cout << "{ " << position[0] << ", " << position[1] << " }" << std::endl;
    }
    std::cout << std::endl;
}

int main()
{
    vector<vector<int>> input = {
        {1,2,2,3,5},
        {3,2,3,4,4},
        {2,4,5,3,1},
        {6,7,1,4,5},
        {5,1,1,2,4}
    };

    vector<vector<int>> result = pacificAtlantic(input);

    for (auto pair: result){
        std::cout << "{" << pair[0] << ", " << pair[1] << "}, ";
    }
    std::cout << std::endl;

    return 0;
}

ЗЫ: решает эту задачу leetcode.com/...​ific-atlantic-water-flow

when you compare signed and unsigned integer, the signed gets promoted to an unsigned. −5 unsigned is an overflow

C++ он такой игровой. Вот еще, все операции выполняются в unsigned domain, результат умножения с переполнением будет равен 0×001. Верно? верно..?..

int main() {
    unsigned short x = 0xFFFF;
    unsigned short y = x * x;
}

меня тогда в этом контексте больше смущает вопрос зачем писать решение на языке которого толком не знаешь и судя по коду это именно «основательно так»

Я пока что не встречал человека, который бы сказал, что «не знает С++, причем основательно так». Кого не спросишь — «С++ это язык збс, вся проблема в людях, которые его не знают и не имеют хорошего опыта», тонко подразумевая что ну он-то как раз знает и умеет.

Этот ваш литкод дрочи- не дрочи все равно херня получается.
Ищу работу. Заломилось тело индусской наружности, хамским образом ткнуло в литкод и убежало. Я поначалу хотел отморозиться, та думаю ж не, новая страна, это ж не Украина, прийдется делать тестовые.
Сделал.
Два задания.
Сложность о от эн, все как положено. Хештейбл прилепил, связанный список одним циклом прошел. Прогнал на тестовых данных что в задаче. Корнер кейсы проверил
Все красиво.
Отправил.
Оно бодро отрапортавало что проверило и выдало результат
Первое задание 75 процентов, второе 39.
И никакого намека даже на тестовые данные на которых проганяло. Ничего. То есть хз как его дебажить и где ошибка.
И ладно хрен с ним тем индусом, но не указать со стороны кодилити где ошибка и не выдать набор данных, на котором проганяется, это свинство.
Хрен я это буду еще делать. Пусть ото ищут задротов сами, я в этом больше не участвую.

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

Це фіча. Їм не треба ті, яким треба вказати на їх помилку. Треба ті, хто цю задачу вирішить без помилок. А помилка є. У другій 100% є, у першій 99.9% що є і вона ваша.
Це як би ви написали програму, а вона падає у відповідного відсотку юзерів і ви кажете, що без того, щоб юзери вам не відтворили у вас ту помилку — нічого зробити не можна.
Ні, треба писати, щоб у юзерів працювало правильно. І наскільки я пам’ятаю коділіті — у вас у порівнянні із реальним життям є величезна перевага — ви знаєте, що помилка є ще до того, як ви «в продакшен» вашу програму випустили.

Велика вірогідність що вам не дали усіх деталей, та чекали від вас уточнювальних запитань. Перевірка як ви будите працювати в команді, з умовами задачі, спілкуватися з продуктовою стороною.

це ж codility, там дають декiлька задач, таймер запускається, та крутись як вмiєш

навряд чи бо це звичайний «перший прохідний етап» типу або так або ні

ЗЫ: я якось навіть погодився на шось таке «200 питань сі++ за 45 хвилин онлайн» і навіть почав але там чисто гонка така вчитування у саме питання то до половини далеко не дійшов відписався шось там типу ввічливе «пнх дякую» з того часу намагаюся вгадати саме такі кейзи вже заздалегідь шоб писати «пнх дякую» з мінімальними витратами ресурсів включно з просто ігнором або репортом на спам коли їх там кудло зібралося і всі вирішили «хайріть чувачка» ))

Интересный топик.
Можно сравнить разные реализации на разных языках.
Настало мое время, С#
Один, простой, лаконичный функциональный запрос на LINQ

//input
var arr = new int[] { 1, 2, 2, 3, 3, 5 };
var k = 2;

//output
var result = arr.GroupBy(x => x)
                       .Select(x => new { Num = x.Key, Count = x.Count() })
                       .OrderByDescending(x => x.Count)
                       .Take(k)
                       .Select(x => x.Num);

Linq и прочие библиотеки вроде как не приветствуются при подобных заданиях.

с другой стороны если это работает то имхо это не так плохо особенно (как я надеюсь) если автор может ещё и (достаточно) внятно объяснить как это работает (конкретная конструкция)

я бы б брал )) имею дело с толпой «других» пишущих то что не могут объяснить часто от слова совсем ни чего личного просто бизнес

ЗЫ: что интересно в стройке та же ж история

Не завжди, скоріш за все це субʼєктивно. Якщо людина може пояснити як працює та чому він використав те чи інше, то ок. Я би дозволяв.
Мені більш цікаво зрозуміти як йде думка, як ми прийшли до цього рішення, чому воно гірше/краще ніж інше. Прийти чи придумати алгорітм складніше ніж його закодувати

Не зміг знайти у вас в main гілці рішення, але побачив щось за тегом v1.8 — github.com/...​uent_elements/Solution.kt

~20к записей мы вероятно будем брать из базы, поэтому я бы решал на уровне запроса.

SELECT COUNT(*) as `count`, `number` FROM `numbers` GROUP BY `number` ORDER BY `count` DESC LIMIT k

На leetcode також є багато задачок с SQL і є набагато хитріші)

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

решение на питоне:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:         return [num for num, freq in Counter(nums).most_common(k)]

most_common

Это не декларативный стиль.
Важно ведь не только кратко и выразительно реализовать задачу, важно чтобы реализация была достаточно гибкой для новых изменений. Так вот прелесть sql и с# (linq) что он выписывает алгоритм как композицию из простейших функциональных преобразований.
Например, сегодня задача звучит как «собрать 5 наиболее частых сигналов с датчика за период»
А завтра
«Выяснилось что датчики имеют погрешность −2/+2»
В декларативном стиле сделать изменения элементарно. Верчу как хочу.
Как встроить в most_common округление — не понятно, потому что это ситуативный пайтоновский костыль.

Одне з найбільш наглядних рішень тут, дуже гарно демонструє переваги SQL при вирішенні деяких типів задач.

Кому цікаво, так виглядає O(n * log k) (де n — кількість унікальних елементів у масиві) вирішення цього завдання на Golang (6 ms, 5 MB): Leetcode

type MinHeap [][2]int16

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i][1] < h[j][1] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.([2]int16)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func topKFrequent(nums []int, k int) []int {
	numToCount := make(map[int16]int16)
	for _, num := range nums {
		numToCount[int16(num)]++
	}
	h := make(MinHeap, 0, k)
	for num, count := range numToCount {
		if len(h) != k {
			heap.Push(&h, [2]int16{num, count})
		} else if count > h[0][1] {
			h[0] = [2]int16{num, count}
			heap.Fix(&h, 0)
		}
	}
	result := nums[:k]
	for i := 0; i < k; i++ {
		result[i] = int(h[i][0])
	}
	return result
}
return the k most frequent elements.
for(let i = nums.length; result.length < k; i—) {
result = result.concat(frequencies[i] || [])
}

Так тут повертається не рівно k елементів.
Не люблю такі синтетичні задачі, які відірвані від реалій та рахують просто складність алгоритму в вакуумі, тому можна і concat ліпити, при чому і з пустим масивом, замість push.apply чи прямих індексів на ініціалізованому масиві. Пам’ять те ж саме- може і рахують розмір кучі, але не навантаження на GC.

З тими вхідними умовами, можна взагалі цей цикл не робити і одразу обирати той набір «частот» де їх >=k, обчислюючи це в основному циклі.

Ви абсолютно праві, це одна із слабких місць другого рішення. Якщо оптимізувати його, то все можна отримати непоганий результат. Діліться вашим варіантом оптимізації з цифрами та метриками

Замість конкату можна заюзати сет і додавати значення в нього, перевіряючи size того сету. Я нижче скидав приклад з результатами.

Якщо піти далі і з умов що рішення гарантовано унікальне, тобто не може бути ситуації коли результат це масив з більше ніж k елементів, то цей останній цикл також можна прибрати. Тоді джаваскріптова реалізація буде вкладатися в 74 ms та 44.3 MB пам’яті.

За допомогою такого розв’язання ми отримуємо результат за 100 мс з використанням 48 мб пам’яті.
то все можна отримати непоганий результат.

Якщо рефакторити приблизно те, що є то 73 ms(96.39%) 43.4 MB(98.33%)
leetcode.com/...​ts/submissions/868205952
Хоча ці метрики пальцем в небо (вибивало 62мс, як сабітнув, то стало 73мс), та і на таких малих вхідних даних не буде видно переваг.
89 ms (79.66%) 42.6 MB (Beats 99.97%)
Краще по пам’яті, гірше по бенчмарку
leetcode.com/...​ts/submissions/868198566
Якщо забити локально в бенчмарк на константному рандомному масиві в 1000 елементів, то такі результати:

topKFrequent original x 6,939 ops/sec ±1.81% (79 runs sampled)
topKFrequent refactored x 15,647 ops/sec ±2.02% (81 runs sampled)
topKFrequent leetcode top solution x 5,279 ops/sec ±1.95% (77 runs sampled)
Fastest is topKFrequent refactored

Process finished with exit code 0

Такие задачи сейчас хорошо решаются с появлением стримов (ява) как тут уже приводили примеры. Сильно сокращает количество кода при относительно неплохой скорости.
На литкоде основные метрики это скорость выполнения и количество памяти, но в жизни то это все нужно еще и поддерживать. Получается другие метрики и другие решения.

Рішення від ChatGPT, але не перевіряв :)

from collections import Counter
import heapq

def top_k_frequent(nums, k):
# Use the Counter class to count the frequency of each element in the list
frequency_count = Counter(nums)

# Convert the frequency count dictionary into a list of tuples, where each tuple
# consists of the element and its frequency
frequency_list = [(element, frequency) for element, frequency in frequency_count.items()]

# Use the heapq module to find the k most frequent elements
# We use the negated frequency as the key to sort the elements by decreasing frequency
top_k = heapq.nlargest(k, frequency_list, key=lambda x: -x[1])

# Extract the elements from the list of tuples and return them in a separate list
return [element for element, frequency in top_k]

This solution has a time complexity of O(n log(k)), which is better than the required O(n log(n)) time complexity. It first counts the frequency of each element in the list using the Counter class, which has a time complexity of O(n). It then uses the heapq.nlargest function to find the k most frequent elements, which has a time complexity of O(k log(k)). The final step of extracting the elements from the list of tuples has a time complexity of O(k). Therefore, the overall time complexity of this solution is O(n + k log(k) + k) = O(n + k log(k)).

PS Як ви код вставляєте? Тег code не працює.

PS Як ви код вставляєте? Тег code не працює.
pre

Нічого так навіть. В міру коротко, в міру зрозуміло, з коментами. Щодо О() в поясненні трохи поплутало грішне з праведним, але то таке.

Треба визнати, що алгоритмічні співбесіди ChatGPT пройде краще більшості з нас.

ChatGPT крута та дуже потужна річь, але має проблеми з поясненням та інколи не вчитується в контекст питання або навмисне спрощує. Експерементував з ним і ставив одну та туж саму задачу двічі, але другий раз додав частку «не», яка змінила сути запиту в корені. Наприклад,
1 — видати Н унікальних чисел з массиву
2 — видати Н не унікальних чисел з массиву
Обидва рази рішення були однакові(

Я не дуже впевнений в самій реалізації на пітоні але це найпростіше рішення що задовольняє вимогам «краще ніж O(n log(n))».

Рекомендовано на літкоді в їх рішеннях також.

Робимо dictionary як і в 1 та 2 прикладах. Потім нам терба min heap щоб порахувати top k max елементів. І потім треба повернути ці k елементів.

Але буде O(n) + O(n log(k)) + O(k log(k)) (якщо повертати елементи з heap через poll()) по суті O(n log(k))
Реалізація на C# leetcode.com/...​ts/submissions/628498385, можливо не найкоротша

але не перевіряв

Не работает, top_k([1,1,1,2,2,3],2) == [3, 2]

# We use the negated frequency as the key to sort the elements by decreasing frequency

Лолшто, зачем, нафига?

До недавнего времени в C# не было heap, в задачах на литкоде на это тему приходилось или самому ее писать или мучиться со всякими SortedDictionary
Зато сейчас меня в 3 ночи разбудить , я закрытыми глазами Heap реализую со всеми основными операциями
Ну и в .net PriorityQueue уже подвезли которая как min-heap реализована

Зы: конкретно в этой задаче можно и без heap, но там есть похожая задача где надо вернуть топ-к из потока, т.е. данных может быть бесконечно много, там словарики не позаполняешь

Я просто один раз її зробив, як дуже спрощений віріант .net PriorityQueue і копіював в кожне рішення :)). На той час вже був .net 6, але на літкоді ще був .net 5 :)

Рішення з Heap яке не використовує додаткову пам’ять. O(N*logN)
29ms/13.3Mb

leetcode.com/...​ts/submissions/867684643

#include <algorithm>
#include <utility>

class Solution {
public:
    static int pop_minimal(vector<int>& nums) {
        std::pop_heap(std::begin(nums), std::end(nums));
        auto ret = nums.back();
        nums.pop_back();
        return ret;
    }

    static bool freq_cmp(const std::pair<int,int>& l, const std::pair<int,int>& r){
        return l.second > r.second;
    }

    static void add_freq(std::vector<std::pair<int, int>>& freq, int k, const std::pair<int,int>& value) {
        freq.push_back(value);
        std::push_heap(freq.begin(), freq.end(), freq_cmp);
        if (freq.size() > k) {
            std::pop_heap(freq.begin(), freq.end(), freq_cmp);
            freq.pop_back();
        }
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        if (nums.size() == 0)
            return {};

        std::make_heap(std::begin(nums), std::end(nums));

        std::vector<std::pair<int, int>> freq;

        std::pair<int,int> current = std::make_pair(pop_minimal(nums), 1);
        while(nums.size() > 0) {
            int value = pop_minimal(nums);
            if (value == current.first) {
                current.second++;
            } else {
                add_freq(freq, k, current);
                current = std::make_pair(value, 1);
            }
        }
        add_freq(freq, k, current);
        
        vector<int> ret;
        ret.reserve(k);
        for(const auto& f : freq)
            ret.push_back(f.first);

        return ret;
    }
};

підфиксив, тепер по пам’яті beats 100%
27ms/13.2Mb
leetcode.com/...​ts/submissions/867691285

Ще одне рішення з 13.1Mb пам’яті (beats 100%)
leetcode.com/...​ts/submissions/867709492
та мені здається що щось вони не те міряють з пам’яттю, бо коли я резервую пам’ять під частоти, щоб виключити декілька алокацій вектора, потреба у пам’яті росте
ось приклад
leetcode.com/...​ts/submissions/867713078

тут я використовую для результата вхідний массив, по пам’яті це найкращій результат
27ms/13.1Mb
leetcode.com/...​ts/submissions/867714461

Чому в Leetcode критерії оцінки тільки час і пам’ять,
а не кількість рядків коду, чи об’єм файлу з кодом?
Тобто простині вітаються?

Якщо встигнеш на интервью те все написати.
Але так, деякi задачi потребують занадто багато коду.

Скажу вам як інтервьювер, якщо ви знайшли гарне рішення, змогли його добре артикулювати (намалювати, пояснити, проговорити його едже кейси та інше) — не страшно невстигнути запрограммувати. Набагато важливіше вміти правильно мислити а ніж швидко писати код

Це не кругом так. Трохи не встиг — до побачення. Десь код i запускати не потрiбно.

Інтервʼю це завжди стрес, а якщо вас просять виконати задачу не в IDE, а в вебредакторі без звичних вам конфігурацій (автодоповнень, підсвітки, та інше) — це нормально не встигнути щось зробити, зʼоріентуватися, почати тупити, навіть якщо це не звично вам.

Мета та низка iнших — код потрiбно проранити i вiн потрiбен працювати.

Також усякi онлайн тести по типу codesignal та iншi.

Хакерранк та кодерпад вже вмiють в автодоповнення бтв.

Я мав на увазi що кругом по рiзному.

На крайньому интервью, наприклад, дали задачку на графи, вiдразу сказали, що код запускати не будемо. Почав будувати граф, сказали забити та не витрачати час, нехай це вже є, тiльки структуру намалюй. Окей, нема питань. З наданих прикладiв можна було пiти простим шляхом, але пiйшов складним, бо чує дупа фолловап, як i пояснив, ок, прийняли. Далi були ще пара фолловапiв, останнiй був на кшалт Bus Routes (LC hard), який я вже пояснював на пальцях без коду. Залiк отримав.

А десь робочий код та покритi корнеркейси — bare minimum. Якщо задача не потребує багато коду, то ок. Iнакше гайки.

щоб не змушувати всіх пропускати свої сабмішни через мініфікатори

Щодо кількості рядків коду чи об’єму файлу з кодом є один простий трюк, рекомендований професійними літкодерами та попаданцями в фаанг: пишіть на Python. Як не крути, код буде коротший за С++ чи Java. Тормозний, звичайно, але алгоритм на ньому можна показати, про О-нотацію поговорити, а менша кількість часу на набивання букв на клавіатурі може додати час на подумати.

Дуже цікаве питання, ніколи ним не задавався. На проектах майже завжди є якийсь код аналізатор, який говорить про складність коду та майбутню його підтримку. Було би цікаво подивитися на такі метрики для топ рішень

Ура, нарешті на ДОУ класні технічні статті по літкоду!

Нижче моя реалізація на С++. Бігає за 7 мс і їсть 13.9 МБ пам’яті, це б’є 99.98% рішень по швидкості (leetcode.com/...​ts/submissions/867442844)

Підхід той же, що і у автора, проте додано кілька брудних хаків:
1. Для обох контейнерів замість map обрано захардкожені масиви на 20000 елементів. Згідно обмежень задачі їх вистачить, а бігати по всього 20к елементів, що лежать у пам’яті підряд, буде швидше ніж вставляти/шукати в мапі, навіть якщо той мап обіцяє О(1) складність операцій.

2. Для повернення результату перевикористовується вхідний масив, це дає можливість уникнути виділення пам’яті для масиву результату.

3. Забиваємо на звільнення виділеної пам’яті для другого контейнера при виході з функції.

За підхід #2 і #3 в продакшн-коді треба бити ломакою по руках і відправляти назад в молодшу школу. Але на літкоді таке дає іноді кілька мілісекунд виграшу, що зайвий раз доводить, що між літкодом та продакшн-кодом — прірва.

vector<int> topKFrequent(vector<int>& nums, int k) {
        std::array<int, 20000> freq;
        freq.fill(0);
        
        for (int& i : nums)
            ++freq[i + 10000];
        
        std::array<std::list<int>*, 20000> back_freq;
        back_freq.fill(nullptr);

        for (int i = 0; i < freq.size(); ++i)
        {
            if (freq[i] == 0)
                continue;

            if (back_freq[freq[i]] == nullptr)
                back_freq[freq[i]] = new std::list<int>();

            back_freq[freq[i]]->push_back(i);
        }
        
        nums.resize(k);
        int added = 0;
        for (int i = back_freq.size() - 1; i >= 0 && added < k; --i)
        {
            if (back_freq[i] == nullptr)
                continue;

            while (added < k && back_freq[i]->empty() == false)
            {
                nums[added++] = back_freq[i]->back() - 10000;
                back_freq[i]->pop_back();
            }
        }
        
        return nums;
    }
Для обох контейнерів замість map обрано захардкожені масиви на 20000 елементів.

Легким рухом руки O(n) по пам’ятi перетворюється в O(1) xD

Дякую за статтю! Нам треба більше алгоритмічно-обізнаних людей в індустрії.

Ця задача класно вирішується через структуру даних heap (PriorityQueue в Java). Розвʼязок є в моєму репозиторії з задачками LeetCode

Можна витратити трохи більше пам’яті, але виграти в швидкості за рахунок того, що можливих чисел всього 20_000 і їх можна покласти в масив замість мапи зі зсувом на 10_000
leetcode.com/...​ts/submissions/867031794

Top K элементов делается за линейное время с помощью алгоритма quickselect.

Маєте рацію, але не забувайте, що в гіршому кейсі ви прийдете до O(n^2)

якщо робити шафл перед тим як прогоняти алгоритм то ймовірність натрапити на кейс з n^2 — майже неймовірна, шафл також O(n)

Підхід тий самий, як і в 2 варіанті, але трохи краще по «папугам» (як рантайм так і пам’ять). Можливо на останньому етапі можна якось більш оптимально зробити, але не думаю що то повпливає дуже на швидкодію. Ну і можна спробувати for ... of та while поміняти на for let.

var topKFrequent = function (nums, k) {
  const freqs = new Map()
  const counts = new Map()

  for (const el of nums) {
    const newCount = (counts.get(el) || 0) + 1
    counts.set(el, newCount)
    freqs.set(newCount, freqs.has(newCount) ? freqs.get(newCount).add(el) : new Set([el]))
  }

  let cursor = freqs.size
  const resultSet = new Set()
  while (cursor >= 0 && resultSet.size < k) {
    const currentSet = freqs.get(cursor)

    for (const item of currentSet) {
      resultSet.add(item)
    }
    cursor--
  }

  return Array.from(resultSet).slice(0, k)
}

leetcode.com/...​ts/submissions/866988768

Для жаваскріптових троху ще додав покращень і прибрав другий цикл. leetcode.com/...​ts/submissions/867748204.
Завдяки тому, що тесткейси там явно не все покривають, тепер по часу «Beats 95.85%», по пам’яті «Beats 91.55%». :)

Але можливо мої тест кейси не підпадають під умову що

It is guaranteed that the answer is unique.

одночасно з умовою

You may return the answer in any order.
Якщо складність цього алгоритму дорівнює o(n), а попередня складність Θ(n log(n)), то чому o(n), що мала б бути простішою і швидшою за перший, виявилася повільнішою?

Ймовірно тому що push до frequencies в даному випадку не є завжди О(1). frequencies буде перерозподілятись з O(n) витратами на копіювання на визначених двіжком межах довжини. Прискорення буде відчутним якщо створити array з одразу заданою довжиною.

то чому o(n), що мала б бути простішою і швидшою за перший, виявилася повільнішою

А чому при сортуваннi малих масивiв переходять вiд quicksort до бiльш повiльних алгоритмiв в О нотації?
Константи мають значення.

Невеличкий лайфхак з користання Leetcode:
коли ви вже розв’язали задачу, то можна клікнути на стовпчик тієї діаграми з розподілом по часу чи по пам’яті, і вам буде показано типовий код, який потрапив в цю категорію. Наприклад, кращий за часом виконання код для цієї задачі виглядає так:

var topKFrequent = function(nums, k) {
    const frequencyMap = nums.reduce((accumulator, curr) => {
        return accumulator.set(curr, accumulator.get(curr) + 1 || 1);
    }, new Map());

    return Array.from(frequencyMap).sort((a, b) => b[1] - a[1]).slice(0, k).map(elem => elem[0]);
};

Дякую за цей лайфхак. Полюбляю аналізувати та порівнювати код щоб зрозуміти чому в той чи іншій ситуації він працює краще/швидше/і тд

В пайтоні переміг декларативний світ (це не топ за часом, але в 1%)

class Solution:

def topKFrequent(self, nums: List[int], k: int) -> List[int]:

return list(zip(*collections.Counter(nums).most_common(k)))[0]

Це рішення на співбесіді не проканало б. Уявіть цей діалог:
-Як знайти Top K Frequent Elements?
-Давайте викличемо функцію «most_common(k)» !

це не буде відрізнятись від того, що ви побудуєте хіп і у нього викличете метод n_largest, що most_common і робить неявно

Буде, бо якщо ви побудуєте хіп, то ви знаєте, що таке хіп. Ймовірно навіть знаєте складність його операцій (тому його і застосовуєте). А викликати бібліотечну функцію, яка (так вже сталося) зразу видає результат — ну, таке

Згоден з вами. Думаю якщо хтось використав виклик бібліотечної функции (наприклад most_common(k)), то наступне питання було би пояснити як вона працює підкапотом та чи можете ви її написати самі.

для мене це було б ідеальне рішення на співбесіді, бо кандидат добре знає вбудований функціонал, та не буде знову вигадувати велосипеди. Плюсом буде, якщо пояснить як воно в теорії працює під капотом.

Навіщо стільки перетворень?

 return [num for num, freq in Counter(nums).most_common(k)]

Нечитабельний говнокод. Краще на 1% повільніший але читабельний.

Наприклад, кращий за часом виконання код для цієї задачі виглядає так:

А на великих вхідних даних (1000 чисел) на локальному бенчмарку він десь там ззаду. Тому цей літкод сферична шляпа в вакуумі.

topKFrequent original x 7,642 ops/sec ±2.83% (82 runs sampled)
topKFrequent refactored x 17,253 ops/sec ±1.29% (88 runs sampled)
topKFrequent top x 5,917 ops/sec ±1.61% (84 runs sampled)
Fastest is topKFrequent refactored
github.com/...​frequent-elements/test.js

але .sort() точно не швидше, ніж O(n*logn), тому не повинно підходити за умовами задачі, хіба не так?

Не повинно, але підходить і навіть має топовий час. Це проблема літкоду — вони не аналізують алгоритм на О(), а лише запускають його, при чому на достатньо малих вхідних даних. В результаті перемагає не те, що має краще О(), а те, що має більше брудних хаків і заточки на літкодове тестове середовище. А ганяти на великих вхідних даних їм економічно не вигідно (хоча могли б це робити хоча б для платних користувачів).

Підписатись на коментарі