[LeetCode] 1203. Sort Items by Groups Respecting Dependencies #1203

grandyang · 2019-05-30T16:32:54Z

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 同步地址:

#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 题目讲解汇总(持续更新中...)

The text was updated successfully, but these errors were encountered: