JavaScript | LeetCode

Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard

Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.

Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.

Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

👨‍💻 Алгоритм:

1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.

2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.

3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.

😎 Решение:

var sortItems = function(n, m, group, beforeItems) {
    let groupId = m;
    for (let i = 0; i < n; i++) if (group[i] === -1) group[i] = groupId++;

    const itemGraph = new Map();
    const groupGraph = new Map();
    const itemIndegree = Array(n).fill(0);
    const groupIndegree = Array(groupId).fill(0);
    for (let i = 0; i < n; i++) itemGraph.set(i, []);
    for (let i = 0; i < groupId; i++) groupGraph.set(i, []);

    for (let curr = 0; curr < n; curr++) {
        for (const prev of beforeItems[curr]) {
            itemGraph.get(prev).push(curr);
            itemIndegree[curr]++;
            if (group[curr] !== group[prev]) {
                groupGraph.get(group[prev]).push(group[curr]);
                groupIndegree[group[curr]]++;
            }
        }
    }

    const itemOrder = topologicalSort(itemGraph, itemIndegree);
    const groupOrder = topologicalSort(groupGraph, groupIndegree);
    if (itemOrder.length === 0 || groupOrder.length === 0) return [];

    const orderedGroups = new Map();
    for (const item of itemOrder) {
        if (!orderedGroups.has(group[item])) orderedGroups.set(group[item], []);
        orderedGroups.get(group[item]).push(item);
    }

    const answerList = [];
    for (const groupIndex of groupOrder) {
        if (orderedGroups.has(groupIndex)) answerList.push(...orderedGroups.get(groupIndex));
    }

    return answerList;
};

function topologicalSort(graph, indegree) {
    const visited = [];
    const stack = [];
    for (const [key] of graph.entries()) if (indegree[key] === 0) stack.push(key);

    while (stack.length > 0) {
        const curr = stack.pop();
        visited.push(curr);
        for (const next of graph.get(curr)) {
            indegree[next]--;
            if (indegree[next] === 0) stack.push(next);
        }
    }

    return visited.length === graph.size ? visited : [];
}

Ставь 👍 и забирай 📚 Базу знаний

473 views09:02