1203. Sort Items by Groups Respecting Dependencies

There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it’s equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.

Return a sorted list of the items such that:

  • The items that belong to the same group are next to each other in the sorted list.
  • There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).

Return any solution if there is more than one solution and return an empty list if there is no solution.

Example 1:

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]

Example 2:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
Output: []
Explanation: This is the same as example 1 except that 4 needs to be before 6 in the sorted list.

Constraints:

  • 1 <= m <= n <= 3 * 104
  • group.length == beforeItems.length == n
  • -1 <= group[i] <= m - 1
  • 0 <= beforeItems[i].length <= n - 1
  • 0 <= beforeItems[i][j] <= n - 1
  • i != beforeItems[i][j]
  • beforeItems[i] does not contain duplicates elements.

这道题给了n个结点,说是其属于m个组,即群组序号在 [0, m-1] 之间,但是又说了还存在一些结点不属于任何的群组,其群组号为 -1,这个需要稍后做些特殊的处理。题目同时还说了可能有的群组中没有结点,现在让给所有的结点进行排序,需要满足一些特定的条件:属于同一个群组的结点必须排在一起,这里还有一个 beforeItems 数组,表示 beforeItems[i] 中的所有结点必须排在结点i的前面,若无法满足这些条件,则返回空数组。这是一道有向图的排序问题,一般都是要使用拓扑排序 Topological Sort 来做,这里比较麻烦的是存在不同的群组,之间可能并不连通,可能需要多次的拓扑排序。不过这里的 beforeItems 数组倒是有可能把不同群组的结点连接起来,这里进行两次拓扑排序,分别是针对群组层面和结点层面。既然要针对群组层面,就要先处理一下那些不属于任何群组的结点,因为其群组号为 -1,不方便处理,这里可以从m开始,分别赋一个不同的值,这样所有的群组号就是正数了。然后就可以新建图的结构了,这里还是用邻接链表的形式来存有向图,用 graphGroup 和 graphItem 分别表示群组和结点的图结构,同时用两个对应的入度数组 inGroup 和 inItem。接下来就是建立图结构了,遍历每个结点i,先找出其属于哪个群组,这里用 to_group 表示,然后就是遍历其对应的 beforeItems 中的结点j,因为这些结点必须在结点i之前,所以它们都应该连到i。对于每个结点j,找出其属于哪个群组,用 from_group 来表示,若此时i和j属于不同的两个群组,且之前二者没有建立联系,则此时将二者的群组连接起来,并且对应入度 inGroup 自增1,这是更新了群组的图结构。接下来还要更新结点的图结构,若二个结点没有相连,则将j连到i,并且i的入度自增1。

当群组图和结点图都建立好了之后,就可以进行拓扑排序了,将排序的过程放到一个子函数中,这样就可以复用代码了。先来看如何进行拓扑排序,可以用 BFS 或者 DFS 来遍历有向图。这里用 BFS 来做,借助队列 queue 来遍历,遍历入度数组,将所有入度为0的结点都放入 queue 中。进行 while 循环,取出队首元素t,将其加入结果 res 中,然后遍历和其所有相连的结点 next,将其对应的入度值减1,若减到0了,则将该结点加入 queue 中。遍历完成了之后,再次检查入度数组,若此时还有大于0的入度值,则表示可能出现环,返回空数组,否则就返回结果 res 即可。在分别得到了群组和结点的有序排列 group_sorted 和 item_sorted 之后,先进行判断,若有任意一个为空,则返回空数组。接下来需要将排序后的结点分组进行保存,用一个二维数组 group2item,遍历所有有序的 item,将其放到其对应的群组内。等结点按群组归纳好了之后,就可以排最终的结点顺序了,需要根据排好的群组顺序进行排列,按群组顺序取出其中的所有结点加入结果 res 即可,参见代码如下:

解法一:

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) group[i] = m++;
        }
        vector<unordered_set<int>> graphGroup(m), graphItem(n);
        vector<int> inGroup(m), inItem(n), res;
        for (int i = 0; i < n; ++i) {
            int to_group = group[i];
            for (int j : beforeItems[i]) {
                int from_group = group[j];
                if (from_group != to_group && !graphGroup[from_group].count(to_group)) {
                    graphGroup[from_group].insert(to_group);
                    ++inGroup[to_group];
                }
                if (!graphItem[j].count(i)) {
                    graphItem[j].insert(i);
                    ++inItem[i];
                }
            }
        }
        vector<int> group_sorted = helper(graphGroup, inGroup), item_sorted = helper(graphItem, inItem);
        if (group_sorted.empty() || item_sorted.empty()) return {};
        vector<vector<int>> group2item(m);
        for (int item : item_sorted) {
            group2item[group[item]].push_back(item);
        }
        for (int group_id : group_sorted) {
            for (int item : group2item[group_id]) {
                res.push_back(item);
            }
        }
        return res;
    }
    vector<int> helper(vector<unordered_set<int>>& g, vector<int>& inDegree) {
        vector<int> res;
        queue<int> q;
        for (int i = 0; i < inDegree.size(); ++i) {
            if (inDegree[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int t = q.front(); q.pop();
            res.push_back(t);
            for (int next : g[t]) {
                if (--inDegree[next] == 0) {
                    q.push(next);
                } 
            }
        }
        for (int i = 0; i < inDegree.size(); ++i) {
            if (inDegree[i] > 0) return {};
        }
        return res;
    }
};

我们再来看一种只需要一个图结构的方法,主要参考了 votrubac 大神的帖子,这里需要用一些辅助结点,具体来说,是在所有群组中都加了一个公共的起始结点,和终止结点,所谓的起始结点,就是该结点通向群组内所有的结点,同理,群组内所有的结点都通向终止结点,这样做的好处是可以有一个公用的入度为0的起始结点开始每个群组的拓扑排序,则群组之间不会互相干扰。由于每个群组都要新增两个辅助结点,则总共的结点数就变成了 n + 2*m,这样就只需要一个结点的图结构就行了。这里还是用邻接链表的形式来保存图结构,由于没有查找需求,直接使用一个二维数组即可。每个群组的公用起始结点标号为 n + group[i],终止标号为 n + m + group[i],这样就互不冲突了。遍历所有的结点,若该结点的群组号不是 -1,则将起始结点连到该结点i,且将该结点i连到终止结点。然后再遍历 beforeItems[i] 中的结点j,若结点i和j属于同一个群组,且均不是 -1,则将结点j连到结点i。否则计算结点i的群组号,若其属于 -1,则用i,否则用其起始结点 n + group[i],同理,对于结点j进行相同的操作,然后把结点j所在的群组连到结点i所在的群组。

这样图结构就建立好了,可以进行拓扑排序了,这里从 n + 2*m - 1 结点开始往前遍历,因为后面的结点值都是新增的辅助结点,都是群组的起始结点或者终止结点,从这些结点开始拓扑排序,就可以完整保持每个群组内部的结点顺序,同时群组之间的顺序也可以保持。为了和上面的解法区分开来,这里使用 DFS 来遍历。这里用一个状态数组 state,大小为 n + 2*m,有三种状态,0表示还未遍历,1表示开始了遍历,但此时还还在继续遍历和其相连的结点中,2表示已经完成了当前结点的遍历。在递归函数中,首先判断当前结点的状态,若不为0,则继续判断,若为2,则返回 true,否则返回 false(此时表示有环存在,无法拓扑排序)。否则将当前结点状态改为1,遍历所有和其相连的结点 next,并对其调用递归函数,若有任意一个结点返回 false 了,则直接返回 false。结束之后,将当前结点状态改为2,并将结点加入结果 res,返回 true 即可。所有的拓扑排序结束后,此时的顺序是和要求的顺序是相反的,因为在递归中是直接将结点加到 res 末尾了,而不是开头。不过没关系,这里直接整个翻转一下就行了,最后别忘了去掉所有的辅助结点,参见代码如下:

解法二:

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<int> t, res(n), state(n + 2 * m);
        vector<vector<int>> g(n + 2 * m);
        for (int i = 0; i < n; ++i) {
            if (group[i] != -1) {
                g[n + group[i]].push_back(i);
                g[i].push_back(n + m + group[i]);
            }
            for (int j : beforeItems[i]) {
                if (group[i] != -1 && group[i] == group[j]) {
                    g[j].push_back(i);
                } else {
                    int p = group[i] == -1 ? i : n + group[i];
                    int q = group[j] == -1 ? j : n + m + group[j];
                    g[q].push_back(p);
                }
            }
        }
        for (int i = (int)g.size() - 1; i >= 0; --i) {
            if (!helper(g, i, state, t)) return {};
        }
        reverse(t.begin(), t.end());
        copy_if(t.begin(), t.end(), res.begin(), [&](int i) {return i < n;});
        return res;
    }
    bool helper(vector<vector<int>>& g, int i, vector<int>& state, vector<int>& res) {
        if (state[i] != 0) return state[i] == 2;
        state[i] = 1;
        for (int next : g[i]) {
            if (!helper(g, next, state, res)) return false;
        }
        state[i] = 2;
        res.push_back(i);
        return true;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1203

参考资料:

https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/

https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/discuss/402945/C%2B%2B-with-picture-generic-topological-sort

https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/discuss/1106701/C%2B%2B-Two-level-topological-sort.-Peel-off-the-tricky-parts-then-do-normal-TopoSort.

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation