Паттерн KV-VK

В этом уроке ты

Научишься применять новый паттерн на примере задачи по поиску топ k частых элементов.

Пример задачи с собеседования

Представь, что ты на собеседовании, и у тебя есть 30 минут, чтобы решить задачу.

Условие

Дан массив целых чисел nums и число k. Необходимо вернуть k наиболее часто встречающихся элементов.

Ответ можно вернуть в любом порядке.

Пример

Ввод: nums = [5,7,5,6,6,5], k = 2
Вывод: [5,6]
Объяснение: элемент 5 встречается 3 раза, элемент 6 встречается 2 раза, а элемент 7 всего один, поэтому мы возвращаем 5 и 6, так как они топ 2 самых встречающихся элементов.

В чем сложность задачи?

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

Далее возникает вопрос: что делать с полученной хеш-таблицей? Поскольку нам нужны k самых частых элементов, логичным решением будет отсортировать элементы по их частоте. Для этого мы превращаем нашу хеш-таблицу в список пар ключ-значение и сортируем его по убыванию частоты. После этого остается лишь выбрать первые k элементов и вернуть их как результат.

//Время: O(nlogn), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
function topKFrequent(nums, k) {
    // Подсчитываем частоту каждого элемента
    const frequencyMap = new Map();
    for (const num of nums) {
        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
    }

    // Преобразуем записи из Map в массив
    const entries = Array.from(frequencyMap.entries());

    // Сортируем массив по убыванию частоты
    entries.sort((a, b) => b[1] - a[1]);

    // Извлекаем первые k элементов
    const result = [];
    for (let i = 0; i < k; i++) {
        result.push(entries[i][0]);
    }

    return result;
}

using System;
using System.Collections.Generic;
using System.Linq;

//Время: O(nlogn), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
public class Solution {
    public IList<int> TopKFrequent(List<int> nums, int k) {
        // Создаем словарь для подсчета частоты каждого элемента
        Dictionary<int, int> frequencyMap = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (frequencyMap.ContainsKey(num)) {
                frequencyMap[num]++;
            } else {
                frequencyMap[num] = 1;
            }
        }

        // Сортируем словарь по убыванию частоты
        var sortedEntries = frequencyMap.OrderByDescending(entry => entry.Value).ToList();

        // Извлекаем первые k элементов
        List<int> result = new List<int>();
        for (int i = 0; i < k; i++) {
            result.Add(sortedEntries[i].Key);
        }

        return result;
    }
}

//Время: O(nlogn), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
func topKFrequent(nums []int, k int) []int {
    // Подсчитываем частоту
    frequencyMap := make(map[int]int)
    for _, num := range nums {
        frequencyMap[num]++
    }

    // Преобразуем карту в слайс пар
    type entry struct {
        key   int
        value int
    }
    entries := make([]entry, 0, len(frequencyMap))
    for key, value := range frequencyMap {
        entries = append(entries, entry{key, value})
    }

    // Сортируем по убыванию частоты
    sort.Slice(entries, func(i, j int) bool {
        return entries[i].value > entries[j].value
    })

    // Извлекаем первые k элементов
    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = entries[i].key
    }

    return result
}

//Время: O(nlogn), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
func topKFrequent(nums []int, k int) []int {
    // Подсчитываем частоту
    frequencyMap := make(map[int]int)
    for _, num := range nums {
        frequencyMap[num]++
    }

    // Преобразуем карту в слайс пар
    type entry struct {
        key   int
        value int
    }
    entries := make([]entry, 0, len(frequencyMap))
    for key, value := range frequencyMap {
        entries = append(entries, entry{key, value})
    }

    // Сортируем по убыванию частоты
    sort.Slice(entries, func(i, j int) bool {
        return entries[i].value > entries[j].value
    })

    // Извлекаем первые k элементов
    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = entries[i].key
    }

    return result
}

//Время: O(nlogn), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
class Solution {
   public List<Integer> topKFrequent(List<Integer> nums, int k) {
        // Создаем хэш-таблицу для подсчета частоты каждого элемента
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Преобразуем записи (entry) из мапы в список
        List<Map.Entry<Integer, Integer>> entries =
        new ArrayList<>(frequencyMap.entrySet());

        // Сортируем список по убыванию частоты
        entries.sort((a, b) -> b.getValue() - a.getValue());

        // Извлекаем первые k элементов после сортировки
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(entries.get(i).getKey());
        }

        return result;
    }
 }

#Время: O(nlogn), где n — размер входного массива.
#Память: O(n), где n — размер входного массива.
class Solution:
    def top_k_frequent(nums: List[int], k: int) -> List[int]:
    # Подсчитываем частоту каждого элемента
    frequency_map = Counter(nums)
    
    # Сортируем элементы по убыванию частоты
    sorted_entries = sorted(frequency_map.items(), key=lambda x: x[1], reverse=True)
    
    # Извлекаем первые k элементов
    return [entry[0] for entry in sorted_entries[:k]]

Однако такое решение может не устроить интервьюера, поскольку его временная сложность составляет O(nlogn) из-за использования сортировки. Он может попросить найти более оптимальный вариант.

Как решить эффективно?

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

После заполнения этого списка мы просто идем с конца (от самых больших частот к меньшим) и выбираем k чисел. Такой подход позволяет обойтись без лишней сортировки, снижая сложность до O(N).

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public List<int> TopKFrequent(List<int> nums, int k) {
        // ключ - число, значение - сколько раз встретилось
        Dictionary<int, int> count = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }

        // индекс списка - сколько раз встретилось число
        // значение - список чисел, которые встретились столько раз
        List<List<int>> frequencyList = new List<List<int>>(new List<int>[nums.Count + 1]);
        for (int i = 0; i <= nums.Count; i++) {
            frequencyList[i] = new List<int>();
        }
        foreach (var entry in count) {
            int num = entry.Key;
            int freq = entry.Value;
            frequencyList[freq].Add(num);
        }

        // Собираем top k элементов начиная с конца списка
        List<int> result = new List<int>();
        for (int i = frequencyList.Count - 1; i >= 0 && k > 0; i--) {
            foreach (int num in frequencyList[i]) {
                result.Add(num);
                k--;
                if (k == 0) break;
            }
        }
        
        return result;
    }
}

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // ключ - число, значение - сколько раз встретилось
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }

        // индекс массива - сколько раз встретилось число
        // значение - список чисел, которые встретились столько раз
        vector<vector<int>> frequencyList(nums.size() + 1);
        for (auto& [num, frequency] : count) {
            frequencyList[frequency].push_back(num);
        }

        // допустим у нас получился такой frequencyList:
        // 0: []
        // 1: [2, 5]
        // 2: []
        // 3: [4]
        // 4: []
        // 5: []
        // при k = 1 нам нужно вернуть 4
        // для этого проходимся с конца и ищем первые k элементов
        vector<int> result;
        for (int i = frequencyList.size() - 1; i >= 0; i--) {
            for (int num : frequencyList[i]) {
                if (k <= 0) {
                    return result;
                }
                result.push_back(num);
                k--;
            }
        }
        return result;
    }
};

func topKFrequent(nums []int, k int) []int {
    // time: O(n)
    // mem: O(n)

    // ключ - число, значение - сколько раз встретилось
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    // индекс массива - сколько раз встретилось число
    // значение - список чисел, которые встретились столько раз
    frequencyList := make([][]int, len(nums)+1)
    for num, frequency := range count {
        frequencyList[frequency] = append(frequencyList[frequency], num)
    }

    // допустим у нас получился такой frequencyList:
    // 0: []
    // 1: [2, 5]
    // 2: []
    // 3: [4]
    // 4: []
    // 5: []
    // при k = 1 нам нужно вернуть 4
    // для этого проходимся с конца и ищем первые k элементов
    result := []int{}
    for i := len(frequencyList) - 1; i >= 0; i-- {
        for _, num := range frequencyList[i] {
            if k <= 0 {
                return result
            }
            result = append(result, num)
            k--
        }
    }
    return result
}

class Solution {
    public List<Integer> topKFrequent(List<Integer> nums, int k) {
        // ключ - число, значение - сколько раз встретилось
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        // индекс массива - сколько раз встретилось число
        // значение - список чисел, которые встретились столько раз
        List<List<Integer>> frequencyList = new ArrayList<>();
        for (int i = 0; i <= nums.size(); i++) {
            frequencyList.add(new ArrayList<>());
        }
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int num = entry.getKey();
            int freq = entry.getValue();
            frequencyList.get(freq).add(num);
        }

        // допустим у нас получился такой frequencyList:
        // 0: []
        // 1: [2, 5]
        // 2: []
        // 3: [4]
        // при k = 1 нам нужно вернуть 4
        // для этого проходимся с конца и ищем первые k элементов
        List<Integer> result = new ArrayList<>();
        for (int i = frequencyList.size() - 1; i >= 0 && k > 0; i--) {
            for (int num : frequencyList.get(i)) {                
                result.add(num);
                k--;
            }
        }
        
        return result;
    }
}

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # ключ - число, значение - сколько раз встретилось
        count = {}
        for num in nums:
            if num not in count:
                count[num] = 0
            count[num] += 1

        # индекс массива - сколько раз встретилось число
        # значение - список чисел, которые встретились столько раз
        frequencyList = [[] for _ in range(len(nums) + 1)]
        for num in count:
            frequency = count[num]
            frequencyList[frequency].append(num)

        # допустим у нас получился такой frequencyList:
        # 0: []
        # 1: [2, 5]
        # 2: []
        # 3: [4]
        # 4: []
        # 5: []
        # при k = 1 нам нужно вернуть 4
        # для этого проходимся с конца и ищем первые k элементов
        result = []
        for numsList in reversed(frequencyList):
            for num in numsList:
                if k <= 0:
                    return result
                result.append(num)
                k -= 1
        return result

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function topKFrequent(nums, k) {
    // ключ - число, значение - сколько раз встретилось
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }

    // индекс массива - сколько раз встретилось число
    // значение - список чисел, которые встретились столько раз
    const frequencyList = Array(nums.length + 1).fill().map(() => []);
    for (const [num, freq] of count.entries()) {
        frequencyList[freq].push(num);
    }

    // допустим у нас получился такой frequencyList:
    // 0: []
    // 1: [2, 5]
    // 2: []
    // 3: [4]
    // при k = 1 нам нужно вернуть 4
    // для этого проходимся с конца и ищем первые k элементов
    const result = [];
    for (let i = frequencyList.length - 1; i >= 0 && k > 0; i--) {
        for (const num of frequencyList[i]) {            
            result.push(num);
            k--;
        }
    }

    return result;
};

Оценка по времени и памяти

Время: Сначала мы проходимся по nums в цикле, потом создаем пустые списки O(n) и переносим элементы из count в frequencyList O(n). И в конце мы проходимся по frequencyList с конца в начало O(n). Итого, время работы алгоритма — O(n).
Память: Мы используем хеш-таблицу для хранения n уникальных чисел, что требует O(n) памяти. Затем мы создаем список frequencyList, в который переносим все n чисел из nums. Важно отметить, что в каждом вложенном списке число хранится только один раз, а не дублируется. Таким образом, общее количество элементов во всех подсписках не превышает n, потому что каждое число встречается ровно столько раз, сколько оно есть в nums, но при этом присутствует только в одном из подсписков. Мы не создаем новых данных, а лишь перераспределяем n элементов, поэтому frequencyList занимает O(n). Результирующий список имеет размер O(k), где k <= n. Итого: O(n)+O(n)+O(k)=O(n).

Итог:

Время: O(n), где n - размер nums.
Память: O(n),где n - размер nums.

Что дальше

Скорее переходи к решению задач, чтобы применить полученные знания на практике!