【Day 31 】2022-01-11 - 1203. 项目管理

[azl397985856]

1203. 项目管理

入选理由

暂无

题目地址

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

前置知识

• 图论
• 拓扑排序
• BFS & DFS

  题目描述

公司共有 n 个项目和  m 个小组，每个项目要不无人接手，要不就由 m 个小组之一负责。

group[i] 表示第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）小组可能存在没有接手任何项目的情况。

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

同一小组的项目，排序后在列表中彼此相邻。 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。 如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

 

示例 1：

![](https://tva1.sinaimg.cn/large/008eGmZEly1gmkv6dy054j305b051mx9.jpg)

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]] 输出：[6,3,4,1,5,2,0,7] 示例 2：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]] 输出：[] 解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。  

提示：

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] 不含重复元素

[yan0327]

思路： 写不出来，先抄个答案。明天再细看

type Node struct{
    preCount int
    NextIDs []int
}

func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
    groupItems := make([][]int, m+n)
    maxGroupID := m-1
    for i:=0;i<n;i++{
        if group[i] == -1{
            maxGroupID++
            group[i] = maxGroupID
        }
        groupItems[group[i]] = append(groupItems[group[i]], i)
    }

    gItem := make([]Node, n)
    for i:=0; i < n;i++{
        for _, preID := range beforeItems[i]{
            gItem[i].preCount++
            gItem[preID].NextIDs = append(gItem[preID].NextIDs, i)
        }
    }

    gGroup := make([]Node, maxGroupID+1)
    for i:=0; i<n; i++{
        curID := group[i]
        for _,preID := range beforeItems[i]{
            preID := group[preID]
            if curID == preID{
                continue
            }
            gGroup[curID].preCount++
            gGroup[preID].NextIDs = append(gGroup[preID].NextIDs, curID)
        }
    }

    q := make([]int, 0)
    for i,v := range gGroup{
        if v.preCount == 0{
            q = append(q,i)
        }
    }
    retGroup := make([]int, 0)
    for len(q) > 0{
        k := len(q)
        for k>0{
            k--
            curID := q[0]
            q = q[1:]
            retGroup = append(retGroup,curID)
            for _,NextID := range gGroup[curID].NextIDs{
                gGroup[NextID].preCount--
                if gGroup[NextID].preCount == 0{
                    q = append(q,NextID)
                }
            }
        }
    }
    if len(retGroup) != maxGroupID+1{
        return []int{}
    }
    ret := make([]int, 0)
    for j:=0; j <= maxGroupID; j++{
        q = make([]int,0)
        for _,id := range groupItems[retGroup[j]]{
            if gItem[id].preCount == 0{
                q = append(q,id)
            }
        }
        for len(q) > 0{
            k := len(q)
            for k > 0{
                k--
                curID := q[0]
                q = q[1:]
                ret = append(ret, curID)
                for _,nextID := range gItem[curID].NextIDs{
                    gItem[nextID].preCount--
                    if gItem[nextID].preCount== 0 && group[nextID]==retGroup[j]{
                        q = append(q, nextID)
                    }
                }
            }
        }
    }
    if len(ret) != n {
        return []int{}
    }
    return ret
}

时间复杂度：O(n+m) 空间复杂度：O（n+m）

[LeahLuo0903]

思路：第一次写hard题，没有太多思路，先跟着答案走 bool topSort(vector<unordered_set>& al, int i, vector& res, vector& stat) { if (stat[i] != 0) return stat[i] == 2; stat[i] = 1; for (auto n : al[i]) if (!topSort(al, n, res, stat)) return false; stat[i] = 2; res.push_back(i); return true; } vector sortItems(int n, int m, vector& group, vector<vector>& beforeItems) { vector res_tmp, res(n), stat(n + 2 m); vector<unordered_set> al(n + 2 m); for (auto i = 0; i < n; ++i) { if (group[i] != -1) { al[n + group[i]].insert(i); al[i].insert(n + m + group[i]); } for (auto j : beforeItems[i]) { if (group[i] != -1 && group[i] == group[j]) al[j].insert(i); else { auto ig = group[i] == -1 ? i : n + group[i]; auto jg = group[j] == -1 ? j : n + m + group[j]; al[jg].insert(ig); } } } for (int n = al.size() - 1; n >= 0; --n) if (!topSort(al, n, res_tmp, stat)) return {}; reverse(begin(res_tmp), end(res_tmp)); copy_if(begin(res_tmp), end(res_tmp), res.begin(), [&](int i) {return i < n; }); return res; }

[Brent-Liu]

class Solution: def tp_sort(self, items, indegree, neighbors): q = collections.deque([]) ans = [] for item in items: if not indegree[item]: q.append(item) while q: cur = q.popleft() ans.append(cur)

        for neighbor in neighbors[cur]:
            indegree[neighbor] -= 1
            if not indegree[neighbor]:
                q.append(neighbor)

    return ans

def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
    max_group_id = m
    for project in range(n):
        if group[project] == -1:
            group[project] = max_group_id
            max_group_id += 1

    project_indegree = collections.defaultdict(int)
    group_indegree = collections.defaultdict(int)
    project_neighbors = collections.defaultdict(list)
    group_neighbors = collections.defaultdict(list)
    group_projects = collections.defaultdict(list)

    for project in range(n):
        group_projects[group[project]].append(project)

        for pre in pres[project]:
            if group[pre] != group[project]:
                # 小组关系图
                group_indegree[group[project]] += 1
                group_neighbors[group[pre]].append(group[project])
            else:
                # 项目关系图
                project_indegree[project] += 1
                project_neighbors[pre].append(project)

    ans = []

    group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

    if len(group_queue) != max_group_id:
        return []

    for group_id in group_queue:

        project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

        if len(project_queue) != len(group_projects[group_id]):
            return []
        ans += project_queue

    return ans

[li65943930]

class Solution: def tp_sort(self, items, indegree, neighbors): q = collections.deque([]) ans = [] for item in items: if not indegree[item]: q.append(item) while q: cur = q.popleft() ans.append(cur)

        for neighbor in neighbors[cur]:
            indegree[neighbor] -= 1
            if not indegree[neighbor]:
                q.append(neighbor)

    return ans

def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
    max_group_id = m
    for project in range(n):
        if group[project] == -1:
            group[project] = max_group_id
            max_group_id += 1

    project_indegree = collections.defaultdict(int)
    group_indegree = collections.defaultdict(int)
    project_neighbors = collections.defaultdict(list)
    group_neighbors = collections.defaultdict(list)
    group_projects = collections.defaultdict(list)

    for project in range(n):
        group_projects[group[project]].append(project)

        for pre in pres[project]:
            if group[pre] != group[project]:
                # 小组关系图
                group_indegree[group[project]] += 1
                group_neighbors[group[pre]].append(group[project])
            else:
                # 项目关系图
                project_indegree[project] += 1
                project_neighbors[pre].append(project)

    ans = []

    group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

    if len(group_queue) != max_group_id:
        return []

    for group_id in group_queue:

        project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

        if len(project_queue) != len(group_projects[group_id]):
            return []
        ans += project_queue

    return ans

[yetfan]

思路 睡了睡了 =。= 路哥nb

代码

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:

            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

复杂度 时间 O(m+n) 空间 O(m+n)

[feifan-bai]

思路

1. 拓扑排序
2. 确定项目间依赖关系
3. 处理无人负责项目

代码

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:

            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

复杂度分析

• 时间复杂度：O(M+N)
• 空间复杂度：O(M+N)

[laofuWF]

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        for(int i = 0; i < n; i++){
            if(group[i] == -1) {
                group[i] = m++;
            }
        }

        int[] countsGroup = new int[m];
        List<List<Integer>> graphGroups = buildGraphGroups(group, beforeItems, countsGroup, m, n);

        int[] countsItem = new int[n];
        List<List<Integer>> graphItems = buildGraphItems(beforeItems, countsItem, n);

        // to acquire the topologically sorted groups and items
        List<Integer> groupsSorted = topologicalSort(graphGroups, countsGroup);
        List<Integer> itemsSorted = topologicalSort(graphItems, countsItem);
        // to detect any cycle
        if(groupsSorted.isEmpty() || itemsSorted.isEmpty()) return new int[0];

        // to build up the relationship between sorted groups and sorted items
        List<List<Integer>> groupsToItems = new ArrayList<List<Integer>>(m);
        for(int i = 0; i < m; i++){
            groupsToItems.add(new ArrayList<Integer>());
        }
        for(int item : itemsSorted){
            groupsToItems.get(group[item]).add(item);
        }

        // to generate the answer array
        int[] ans = new int[n];
        int idx = 0;
        // to first pick, in front groups, front elements/items 
        for(int curGroup : groupsSorted){
            for(int item : groupsToItems.get(curGroup)) {
                ans[idx++] = item;
            }
        }

        return ans;
    }

    private List<Integer> topologicalSort(List<List<Integer>> graph, int[] counts){
        final int N = counts.length;
        List<Integer> res = new ArrayList<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < N; i++){
            if(counts[i] == 0){
                queue.add(i);
            }
        }

        int count = 0;
        while(!queue.isEmpty()){
            int node = queue.poll();
            res.add(node); 
            count++;
            for(int neighbor : graph.get(node)){
                if(--counts[neighbor] == 0){
                    queue.offer(neighbor);
                }
            }
        }

        return count == N ? res : new ArrayList<Integer>();
    }

    private List<List<Integer>> buildGraphItems(List<List<Integer>> beforeItems, 
                                                int[] counts, 
                                                int n){
        List<List<Integer>> graph = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; i++){
            graph.add(new ArrayList<Integer>());
        }

        for(int i = 0; i < n; i++){
            List<Integer> items = beforeItems.get(i);
            for(int item : items){
                graph.get(item).add(i);
                ++counts[i];
            }
        }

        return graph;
    }

    private List<List<Integer>> buildGraphGroups(int[] group, 
                                                 List<List<Integer>> beforeItems, 
                                                 int[] counts, 
                                                 int m,
                                                 int n){
        List<List<Integer>> graph = new ArrayList<List<Integer>>(m);
        for(int i = 0; i < m; i++){
            graph.add(new ArrayList<Integer>());
        }

        for(int i = 0; i < n; i++){
            int toGroup = group[i];
            List<Integer> fromItems = beforeItems.get(i);
            for(int fromItem : fromItems){
                int fromGroup = group[fromItem];
                if(fromGroup != toGroup){
                    graph.get(fromGroup).add(toGroup);
                    ++counts[toGroup];
                }
            }
        }

        return graph;
    }
}

[MonkofEast]

1203. Sort Items by Groups Respecting Dependencies

Click Me

Algo

1. match unassigned projs to new group
2. construct indeg/neigh for group & proj. Plus construct group_proj mappings
3. first topo sort group, then topo sort projs for each group

Code

class Solution:
    def topoSort(self, items, indeg, neighs):
        que = collections.deque([])
        for item in items:
            if indeg[item] == 0: que.append(item)

        res = []
        while que:
            curr = que.popleft()
            res.append(curr)
            for neigh in neighs[curr]:
                indeg[neigh] -= 1
                if indeg[neigh] == 0: que.append(neigh)

        return res

    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        # match unassigned projs to new group
        max_group_id = m
        for proj in range(n):
            if group[proj] == -1:
                group[proj] = max_group_id
                max_group_id += 1

        # indeg arr & neigh arr & group-proj relationship
        proj_indeg = [0 for _ in range(n)]
        group_indeg = [0 for _ in range(max_group_id)]
        proj_neigh = collections.defaultdict(list)
        group_neigh = collections.defaultdict(list)
        group_proj = collections.defaultdict(list) # what projs does a group have. key: group. val: proj

        for proj in range(n):
            # make a dict about what group has what projs
            group_proj[group[proj]].append(proj)
            # check successive relationship in groups
            for preProj in beforeItems[proj]:
                if group[preProj] != group[proj]:
                    group_indeg[group[proj]] += 1
                    group_neigh[group[preProj]].append(group[proj])
                # not dependency in groups level, add to proj dependency
                else:
                    proj_indeg[proj] += 1
                    proj_neigh[preProj].append(proj)

        #print(max_group_id)
        #print(group_proj)
        #print(group_indeg)
        #print(group_neigh)

        # find the topo sort of groups        
        res = []
        group_que = self.topoSort([i for i in range(max_group_id)], group_indeg, group_neigh)
        if len(group_que) != max_group_id: return []   
        # find the topo sort of projs
        for group_idx in group_que:
            proj_que = self.topoSort(group_proj[group_idx], proj_indeg, proj_neigh)
            if len(proj_que) != len(group_proj[group_idx]): return []
            res += proj_que

        return res

Comp

T: O(v+e)

S: O(v+e)

[xinhaoyi]

1203. 项目管理

有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 -1。项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

同一小组的项目，排序后在列表中彼此相邻。 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。 如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

示例 1：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]] 输出：[6,3,4,1,5,2,0,7] 示例 2：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]] 输出：[] 解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。

思路一

拓扑排序

本题自己完全没有思路，抄的题解的代码，并看懂了它。

这题的核心是首先不同项目item之间存在顺序性，那么可以把不同项目看作结点，这就是一个有向图，我们对有向图使用拓扑排序，得到的序列就是按照项目先后顺序得到的序列，比如：

拓扑排序就是首先排出0入度的结点（这些结点之间顺序随意），然后把这些结点都删了，再排出新的入度为0的结点，以此往复

但是这题还有一个要求是同组的项目要放一起，这个怎么保证呢？我们可以根据项目和组的多对一关系，先遍历每一个项目，对每一个项目都找到他们对应的组A，再找到其前置项目集合对应的又是哪几个组（B、C、D），如果A和B、C、D中某一个是一个组，那么这个B/C/D就不要添加，因为同一个组不存在什么先后，否则的话在这个B/C/D组的邻接表结点中，把A加进去，同时组的入度数组中A对应的入度值加一，维护一个入度数组主要是为了在拓扑排序的时候能够知道各个结点的入度数，从而总是从入度为0的结点开始排序。之后同理也维护好项目的邻接表和入度数组。

这之后就可以把项目和组都进行拓扑排序，得到项目顺序和组顺序，再根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系，之所以需要项目的拓扑排序结果，是因为这个一对多的“多”中，项目也是按照拓扑的顺序按次序排列的，然后我们根据组到项目的一对多关系，把组的拓扑排序结果映射为项目的拓扑排序结果，这个就是我们最终的结果

注意一下拓扑排序是广度优先遍历，而且要检查有向图是否成环，如果成环要输出空的list

代码

public class Solution {

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        // 第 2 步：初始化组和项目的邻接表
        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for (int i = 0; i < m; i++) {
            groupAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            itemAdj[i] = new ArrayList<>();
        }

        // 第 3 步：创建图和统计入度数组
        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        //维护组的入度数组和邻接表
        int len = group.length;
        for (int i = 0; i < len; i++) {
            int currentGroup = group[i];
            for (int beforeItem : beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                //如果这两个项目是同一个组，自然不用分先后顺序
                if (beforeGroup != currentGroup) {
                    //否则注意是把currentGroup插进beforeGroup的邻接表中，因为beforeGroup在前面
                    groupAdj[beforeGroup].add(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }

        //维护图的入度数组和邻接表
        for (int i = 0; i < n; i++) {
            for (Integer item : beforeItems.get(i)) {
                //和上面的组的邻接表维护方法一致
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        // 第 4 步：得到组和项目的拓扑排序结果
        //组的拓扑排序结果
        List<Integer> groupsList = topologicalSort(groupAdj, groupsIndegree, m);
        //如果size为0，说明有向图内部有环（我的方法内部决定的，有环就输出空list
        if (groupsList.size() == 0) {
            return new int[0];
        }
        //项目的拓扑排序结果
        List<Integer> itemsList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemsList.size() == 0) {
            return new int[0];
        }

        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // 之所以需要项目的拓扑排序结果，是因为这个一对多的“多”中，项目也是按照拓扑的顺序按次序排列的
        // key：组，value：在同一组的项目列表
        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        List<Integer> res = new ArrayList<>();
        for (Integer groupId : groupsList) {
            List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
            //把items中的所有元素加入到res中
            res.addAll(items);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    //拓扑排序方法，adj是邻接表，inDegree是入度数组，n是元素总数
    private List<Integer> topologicalSort(List<Integer>[] adj, int[] inDegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        //广度优先遍历，把入度为0的结点全部入队列
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        //出队，把他们加进res中，并且根据邻接表找到他们的后续邻接结点，把这些邻接结点的入度都减1，如果有入度变为0的
        //也入队
        while (!queue.isEmpty()) {
            Integer front = queue.poll();
            res.add(front);
            for (int successor : adj[front]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) {
                    queue.offer(successor);
                }
            }
        }

        //判断是否有环
        if (res.size() == n) {
            return res;
        }
        return new ArrayList<>();
    }
}

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

[Tesla-1i]

class Solution:
def tp_sort(self, items, indegree, neighbors):
q = collections.deque([])
ans = []
for item in items:
if not indegree[item]:
q.append(item)
while q:
cur = q.popleft()
ans.append(cur)

        for neighbor in neighbors[cur]:
            indegree[neighbor] -= 1
            if not indegree[neighbor]:
                q.append(neighbor)

    return ans

def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
    max_group_id = m
    for project in range(n):
        if group[project] == -1:
            group[project] = max_group_id
            max_group_id += 1

    project_indegree = collections.defaultdict(int)
    group_indegree = collections.defaultdict(int)
    project_neighbors = collections.defaultdict(list)
    group_neighbors = collections.defaultdict(list)
    group_projects = collections.defaultdict(list)

    for project in range(n):
        group_projects[group[project]].append(project)

        for pre in pres[project]:
            if group[pre] != group[project]:
                # 小组关系图
                group_indegree[group[project]] += 1
                group_neighbors[group[pre]].append(group[project])
            else:
                # 项目关系图
                project_indegree[project] += 1
                project_neighbors[pre].append(project)

    ans = []

    group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

    if len(group_queue) != max_group_id:
        return []

    for group_id in group_queue:

        project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

        if len(project_queue) != len(group_projects[group_id]):
            return []
        ans += project_queue

    return ans

[haixiaolu]

思路

题解都看不太明白， 先把代码抄上

代码 /Python

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:

            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

• 时间复杂度： O(m + n)
• 空间复杂度： O(m + n)

[JuliaShiweiHuang]

写不出来 是抄的 ”“” class Solution: def tp_sort(self, items, indegree, neighbors): q = collections.deque([]) ans = [] for item in items: if not indegree[item]: q.append(item) while q: cur = q.popleft() ans.append(cur)

        for neighbor in neighbors[cur]:
            indegree[neighbor] -= 1
            if not indegree[neighbor]:
                q.append(neighbor)

    return ans

def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
    max_group_id = m
    for project in range(n):
        if group[project] == -1:
            group[project] = max_group_id
            max_group_id += 1

    project_indegree = collections.defaultdict(int)
    group_indegree = collections.defaultdict(int)
    project_neighbors = collections.defaultdict(list)
    group_neighbors = collections.defaultdict(list)
    group_projects = collections.defaultdict(list)

    for project in range(n):
        group_projects[group[project]].append(project)

        for pre in pres[project]:
            if group[pre] != group[project]:
                # 小组关系图
                group_indegree[group[project]] += 1
                group_neighbors[group[pre]].append(group[project])
            else:
                # 项目关系图
                project_indegree[project] += 1
                project_neighbors[pre].append(project)

    ans = []

    group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

    if len(group_queue) != max_group_id:
        return []

    for group_id in group_queue:

        project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

        if len(project_queue) != len(group_projects[group_id]):
            return []
        ans += project_queue

    return ans

“”“

[Moin-Jer]

思路

---

拓扑排序

代码

---

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Solution {

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for (int i = 0; i < m; i++) {
            groupAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            itemAdj[i] = new ArrayList<>();
        }

        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        int len = group.length;
        for (int i = 0; i < len; i++) {
            int currentGroup = group[i];
            for (int beforeItem : beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != currentGroup) {
                    groupAdj[beforeGroup].add(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (Integer item : beforeItems.get(i)) {
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        List<Integer> groupsList = topologicalSort(groupAdj, groupsIndegree, m);
        if (groupsList.size() == 0) {
            return new int[0];
        }
        List<Integer> itemsList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemsList.size() == 0) {
            return new int[0];
        }

        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        List<Integer> res = new ArrayList<>();
        for (Integer groupId : groupsList) {
            List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private List<Integer> topologicalSort(List<Integer>[] adj, int[] inDegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer front = queue.poll();
            res.add(front);
            for (int successor : adj[front]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) {
                    queue.offer(successor);
                }
            }
        }

        if (res.size() == n) {
            return res;
        }
        return new ArrayList<>();
    }
}

复杂度分析

---

• 时间复杂度：O(m + n)
• 空间复杂度：O(m + n)

[wdwxw]

思路： 这个题目好难，刚进来还没补全前面的知识 想抄个答案，后续补题

class Solution {
public:
    using UMIV = unordered_map<int, vector<int> >;
    using UMII = unordered_map<int, int>;
    using VVI = vector<vector<int> >;
    using VI = vector<int>;
    UMIV sub;
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& befores) {
        for (int j = 0; j < n; j++) {
            if (group[j] == -1) group[j] = m++;
        }

        vector<vector<int> > gg(m);
        for (int j = 0; j < n; j++) gg[group[j]].push_back(j);

        for (int i = 0; i < gg.size(); i++) {
            if (gg[i].size() == 1) {
                int itemId = gg[i][0];
                sub[group[itemId]]= {itemId};
                continue;
            }
            bool f = topoSort(i, gg[i], befores);
            if (f == false) return {};
        }

        VI groups; 
        for (int i = 0; i < m; i++) groups.push_back(i);
        VVI newbefore(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < befores[i].size(); j++) {
                int prevId = group[befores[i][j]];
                if (prevId != group[i]) newbefore[group[i]].push_back(prevId);
            }
        }
        if(!topoSort(m, groups, newbefore)) return {};
        VI rs;
        for (auto v : sub[m]) rs.insert(rs.end(), sub[v].begin(), sub[v].end());
        return rs;
    }

    bool topoSort(int gpid, VI& num, VVI& bef) {
        int n = num.size();
        UMII degree; // 度
        UMIV g; // 图
        for (int i = 0; i < n; i++) {
            degree[num[i]] = 0;
            g[num[i]] = vector<int>();
        }
        for (int i = 0; i < n; i++) {
            int idx = num[i];
            if(bef[idx].size() == 0) continue;
            for (int j = 0; j < bef[idx].size(); j++) {
                int last = bef[idx][j];
                if (degree.find(last) == degree.end()) continue;
                g[last].push_back(idx);
                degree[idx]++;
            }
        }
        VI res;
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (degree[num[i]] == 0) 
                q.push(num[i]);
        }
        while (!q.empty()) {
            int cur = q.front();
            res.push_back(cur);
            if (g[cur].size() != 0) {
                for (int i = 0; i < g[cur].size(); i++) {
                    if (--degree[g[cur][i]] == 0) q.push(g[cur][i]);
                }
            }
            q.pop();
        }
        sub[gpid] = move(res);
        return sub[gpid].size() == n;
    }
};

[CodingProgrammer]

思路

拓扑排序

代码

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Solution {

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        // 第 2 步：实例化组和项目的邻接表
        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for (int i = 0; i < m; i++) {
            groupAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            itemAdj[i] = new ArrayList<>();
        }

        // 第 3 步：建图和统计入度数组
        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        int len = group.length;
        for (int i = 0; i < len; i++) {
            int currentGroup = group[i];
            for (int beforeItem : beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != currentGroup) {
                    groupAdj[beforeGroup].add(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (Integer item : beforeItems.get(i)) {
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        // 第 4 步：得到组和项目的拓扑排序结果
        List<Integer> groupsList = topologicalSort(groupAdj, groupsIndegree, m);
        if (groupsList.size() == 0) {
            return new int[0];
        }
        List<Integer> itemsList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemsList.size() == 0) {
            return new int[0];
        }

        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // key：组，value：在同一组的项目列表
        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        List<Integer> res = new ArrayList<>();
        for (Integer groupId : groupsList) {
            List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private List<Integer> topologicalSort(List<Integer>[] adj, int[] inDegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer front = queue.poll();
            res.add(front);
            for (int successor : adj[front]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) {
                    queue.offer(successor);
                }
            }
        }

        if (res.size() == n) {
            return res;
        }
        return new ArrayList<>();
    }
}

[hdyhdy]

func topSort(graph [][]int, deg, items []int) (orders []int) {
    q := []int{}
    for _, i := range items {
        if deg[i] == 0 {
            q = append(q, i)
        }
    }
    for len(q) > 0 {
        from := q[0]
        q = q[1:]
        orders = append(orders, from)
        for _, to := range graph[from] {
            deg[to]--
            if deg[to] == 0 {
                q = append(q, to)
            }
        }
    }
    return
}

func sortItems(n, m int, group []int, beforeItems [][]int) (ans []int) {
    groupItems := make([][]int, m+n) // groupItems[i] 表示第 i 个组负责的项目列表
    for i := range group {
        if group[i] == -1 {
            group[i] = m + i // 给不属于任何组的项目分配一个组
        }
        groupItems[group[i]] = append(groupItems[group[i]], i)
    }

    groupGraph := make([][]int, m+n) // 组间依赖关系
    groupDegree := make([]int, m+n)
    itemGraph := make([][]int, n) // 组内依赖关系
    itemDegree := make([]int, n)
    for cur, items := range beforeItems {
        curGroupID := group[cur]
        for _, pre := range items {
            preGroupID := group[pre]
            if preGroupID != curGroupID { // 不同组项目，确定组间依赖关系
                groupGraph[preGroupID] = append(groupGraph[preGroupID], curGroupID)
                groupDegree[curGroupID]++
            } else { // 同组项目，确定组内依赖关系
                itemGraph[pre] = append(itemGraph[pre], cur)
                itemDegree[cur]++
            }
        }
    }

    // 组间拓扑序
    items := make([]int, m+n)
    for i := range items {
        items[i] = i
    }
    groupOrders := topSort(groupGraph, groupDegree, items)
    if len(groupOrders) < len(items) {
        return nil
    }

    // 按照组间的拓扑序，依次求得各个组的组内拓扑序，构成答案
    for _, groupID := range groupOrders {
        items := groupItems[groupID]
        orders := topSort(itemGraph, itemDegree, items)
        if len(orders) < len(items) {
            return nil
        }
        ans = append(ans, orders...)
    }
    return
}

[shamworld]

var sortItems = function(n, m, group, beforeItems) {
     const groupItems = new Array(m + n).fill(0).map(() => []);
    // 将未分组自身为一组
    let k = m;
    for (let i = 0; i < n; i++) {
        if (group[i] === -1) {
            group[i] = k++;
        }
        groupItems[group[i]].push(i);
    }
    // 组间关系及入度
    const groupGraph = new Array(m + n).fill(0).map(() => []);
    const groupIn = new Array(m + n).fill(0);
    // 组内关系及入度
    const itemGraph = new Array(n).fill(0).map(() => []);
    const itemIn = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        const curGroupId = group[i];
        for (let beforeIndex of beforeItems[i]) {
            const beforeGroupId = group[beforeIndex];
            if (curGroupId === beforeGroupId) {
                // 组相同，加入组内元素关系及入度
                itemIn[i] += 1;
                itemGraph[beforeIndex].push(i);
            } else {
                // 如果组间关系存在，不重复保存
                if (groupGraph[beforeGroupId].indexOf(curGroupId) >= 0) continue;
                groupIn[curGroupId] += 1;
                groupGraph[beforeGroupId].push(curGroupId);
            }
        }
    }

    /**
     * @param {number[][]} graph 关联关系
     * @param {number[]} inNum 入度
     * @param {number[]} groupItems 组元素或同组内元素
     * @return {number[]}
     */
    const topSort = (graph, inNum, groupItems) => {
        const queue = [];
        // 入度为0的加入队列
        for (let inIndex of groupItems) {
            if (inNum[inIndex] === 0) {
                queue.push(inIndex);
            }
        }
        const temp = [];
        while (queue.length) {
            // 取队首元素
            const index = queue.shift();
            temp.push(index);
            for (let i = 0; i < graph[index].length; i++) {
                // 指向元素的下标
                const inIndex = graph[index][i];
                // 入度减1
                inNum[inIndex] -= 1;
                // 当入度为0时，也加入到队列
                if (inNum[inIndex] === 0) {
                    queue.push(inIndex)
                }
            }
        }
        return temp.length === groupItems.length ? temp : [];
    }
    // 表示所有组
    const groupIds = new Array(m + n).fill(0).map((item, index) => index);
    const groupTopSort = topSort(groupGraph, groupIn, groupIds);
    if (groupTopSort.length === 0) {
        return [];
    }
    let res = [];
    for (let groupId of groupTopSort) {
        const curGroup = groupItems[groupId];
        // 组内可能没有分配任务
        if (curGroup.length === 0) {
            continue;
        }
        if (curGroup.length === 1) {
            // 长度为1，未分组元素，组内无需排序
            res.push(curGroup[0]);
        } else {
            // 长度大于1，组内进行排序
            const itemTopSort = topSort(itemGraph, itemIn, curGroup);
            if (itemTopSort.length === 0) {
                return [];
            }
            res = [...res, ...itemTopSort];
        }
    }
    return res
};

[naomiwufzz]

思路：双层拓扑排序

学习官方题解。首先，要掌握拓扑排序，拓扑排序适用于一个任务中有多个子任务，子任务可能有优先级（但不能互相交叉，能够满足有向无环图）的情况。这题项目管理，说明有的项目要在一些项目之前，其实就很好的满足拓扑排序的定义，但这题，除了项目有顺序，组也有顺序，这个就需要建立双层的图关系，也就是项目图关系和组图关系。项目图关系是题目给出的，那么组图关系是什么呢？其实就是当组里面项目有优先关系的时候，组的优先关系就定了。最后就是没有分组的怎么办呢？没有分组的直接自增地给一个组即可。官方思路非常清晰，但是这题知识点比较多，不是太好想

代码

from collections import deque, defaultdict
class Solution:
    def tp_sort(self, items, indegree, neighbors) -> List[int]:
        res = []
        q = deque()
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            res.append(cur)
            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)
        return res

    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        max_group_id = m
        # 无组的项目，从m开始自增地+1分配给一个组
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        # 项目关系
        project_indegree = defaultdict(int)
        project_neighbors = defaultdict(list)

        # 小组关系
        group_indegree = defaultdict(int)
        group_neighbors = defaultdict(list)

        # 组和项目的对应关系
        group_projects = defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)
            # 每个项目都可能有before
            for pre in beforeItems[project]:
                # 如果pre和project不在一个组，说明pre的组要在project组前面，处理组关系
                # 小组关系图
                if group[pre] != group[project]:
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                # 项目关系图
                else:
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)
        res = []
        # 对组拓扑排序，因为无组的都分配了一个组，所以现在有max_group_id个组
        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)
        # 如果排序完长度和原来不一致，说明无法正确拓扑排序
        if len(group_queue) != max_group_id:
            return []
        for group_id in group_queue:
            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)
            if len(project_queue) != len(group_projects[group_id]):
                return []
            res += project_queue
        return res

复杂度分析

• 时间复杂度：O(m+n) m是边数，n是顶点数
• 空间复杂度：O(m+n)

[wangzehan123]

Java Code:

class Solution {
       public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        //不属于任何组的任务指派个独立组id
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        List<Set<Integer>> groupRsList = new ArrayList<>();
        List<List<Integer>> groupItems = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            groupItems.add(new ArrayList<>());
            groupRsList.add(new LinkedHashSet<>());
        }
        for (int i = 0; i < n; i++) {
            groupItems.get(group[i]).add(i);
        }
        //下一个组
        List<Set<Integer>> groupNextList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            groupNextList.add(new HashSet<>());
        }
        //下一个任务
        List<Set<Integer>> itemNextList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            itemNextList.add(new HashSet<>());
        }
        //任务入度
        int[] itemIn = new int[n];
        for (int i = 0; i < beforeItems.size(); i++) {
            List<Integer> beforeItem = beforeItems.get(i);
            itemIn[i] = beforeItem.size();
            for (Integer item : beforeItem) {
                itemNextList.get(item).add(i);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        int handleItemCount=0;
        for (int i = 0; i < n; i++) {
            if (itemIn[i] == 0) {
                queue.add(i);
                handleItemCount++;
            }

        }
        //组入度
        int[] groupIn = new int[m];
        Set<Integer> nextQueue = new HashSet<>();

        while (!queue.isEmpty()) {
            int item = queue.poll();
            groupRsList.get(group[item]).add(item);
            Set<Integer> nextList = itemNextList.get(item);
            for (Integer nextItem : nextList) {
                itemIn[nextItem]--;
                if (itemIn[nextItem] < 0) {
                    return new int[0];
                }
                if (group[nextItem] != group[item]) {
                    if(!groupNextList.get(group[item]).contains(group[nextItem])){
                        groupNextList.get(group[item]).add(group[nextItem]);
                        groupIn[group[nextItem]]++;
                    }

                }
                if (itemIn[nextItem] == 0) {
                    handleItemCount++;
                    nextQueue.add(nextItem);
                }

            }
            if (queue.isEmpty()) {
                queue.addAll(nextQueue);
                nextQueue.clear();
            }

        }

        if(handleItemCount<n){
            return new int[0];
        }

        int handleGroupCount=0;
        List<Integer> itemRsList  = new ArrayList<>();
        List<Integer> rsList  = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            if(groupIn[i]==0){
                handleGroupCount++;
                rsList.add(i);
                itemRsList.addAll(groupRsList.get(i));
                queue.add(i);
            }
        }

        while (!queue.isEmpty()){
            int groupId=queue.poll();
            Set<Integer> nextList=groupNextList.get(groupId);
            for(Integer nextGroupId:nextList){
                groupIn[nextGroupId]--;
                if(groupIn[nextGroupId]<0){
                    return new int[0];
                }
                if(groupIn[nextGroupId]==0){
                    handleGroupCount++;
                    nextQueue.add(nextGroupId);
                    rsList.add(nextGroupId);
                    itemRsList.addAll(groupRsList.get(nextGroupId));
                }
            }
            if (queue.isEmpty()) {
                queue.addAll(nextQueue);
                nextQueue.clear();
            }

        }
        if(handleGroupCount<m){
            return new int[0];
        }
        int[] rs = new int[n];
        for (int i = 0; i < itemRsList.size(); i++) {
            rs[i]=itemRsList.get(i);
        }
        return rs;
    }
}

[RocJeMaintiendrai]

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        Map<Integer, List<Integer>> gGraph = new HashMap<>();
        Map<Integer, List<Integer>> iGraph = new HashMap<>();
        for(int i = 0; i < group.length; i++) {
            if(group[i] == -1) group[i] = m++;
        }

        int[] itemInDegree = new int[n];
        int[] groupInDegree = new int[m];

        for(int to = 0; to < beforeItems.size(); to++) {
            int toGroup = group[to];
            for(int from : beforeItems.get(to)) {
                itemInDegree[to]++;
                if(!iGraph.containsKey(from)) {
                    iGraph.put(from, new ArrayList<Integer>());
                }
                iGraph.get(from).add(to);
            }
        }

        //build item graph
        for(int to = 0; to < group.length; to++) {
            int toGroup = group[to];
            for(int from : beforeItems.get(to)) {
                int fromGroup = group[from];
                if(gGraph.containsKey(fromGroup)) {
                    gGraph.put(fromGroup, new ArrayList<Integer>());
                }
                if(fromGroup != toGroup) {
                    groupInDegree[toGroup]++;
                    gGraph.get(fromGroup).add(toGroup);
                }
            }
        }

        List<Integer> iList = tpSort(iGraph, itemInDegree, n);
        List<Integer> gList = tpSort(gGraph, groupInDegree, m);

        if(iList.size() == 0 || gList.size() == 0) return new int[0];

        Map<Integer, List<Integer>> groupedList = new HashMap<>();
        for(int item : iList) {
            int grp = group[item];
            if(!groupedList.containsKey(grp)) {
                groupedList.put(grp, new ArrayList<Integer>());
            }
            groupedList.get(grp).add(item);
        }

        int i = 0;
        int[] ans = new int[n];
        for(int grp : gList) {
            if(!groupedList.containsKey(grp)) continue;
            for(int item : groupedList.get(grp)) {
                ans[i] = item;
                i++;
            }
        }
        return ans;
    }

    public List<Integer> tpSort(Map<Integer, List<Integer>> graph, int[] inDegree, int count) {
        List<Integer> ans = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < inDegree.length; i++) {
            if(inDegree[i] == 0) q.offer(i);
        }
        while(!q.isEmpty()) {
            int cur = q.poll();
            ans.add(cur);
            if(!graph.containsKey(cur)) continue;
            for(int next : graph.get(cur)) {
                inDegree[next]--;
                if(inDegree[next] == 0) q.offer(next);
            }
        }
        return count == ans.size() ? ans : new ArrayList<>();
    }
}

复杂度分析

• 时间复杂度：O(m + n)
• 空间复杂度：O(m + n)

[rzhao010]

Thoughts Topological sorting

Code

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // step 1: indexing the Item with a group number
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            } 
        }
        // step 2: realize adjacent list
        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for (int i = 0; i < m; i++) {
            groupAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            itemAdj[i] = new ArrayList<>();
        }

        // step 3: create graph and indegree array
        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        int len = group.length;
        for (int i = 0; i < len; i++) {
            int currentGroup = group[i];
            for (int beforeItem: beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != currentGroup) {
                    groupAdj[beforeGroup].add(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (Integer item: beforeItems.get(i)) {
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        // step 4: get the topological sorting results of group and item
        List<Integer> groupList = topologicalSort(groupAdj, groupsIndegree, m);
        if (groupList.size() == 0) {
            return new int[0];
        }
        List<Integer> itemList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemList.size() == 0) {
            return new int[0];
        }

        // step 5: mapping item to group
        // key: group, value: item list
        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item: itemList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        // step 6: substitute the group topologicial result with item's
        List<Integer> res = new ArrayList<>();
        for (Integer groupId: groupList) {
            List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private List<Integer> topologicalSort(List<Integer>[] adj, int[] indegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer front = queue.poll();
            res.add(front);
            for (int successor: adj[front]) {
                indegree[successor]--;
                if (indegree[successor] == 0) {
                    queue.offer(successor);
                }
            }
        }

        if (res.size() == n) {
            return res;
        }

        return new ArrayList<>();
    }
}

Complexity Time: O(m + n^2 + E-group + E-item) Space: O(m + n^2)

[LannyX]

思路

topologicalSort

代码

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // 1：数据预处理，给没有归属于一个组的项目编上组号
        for(int i = 0; i < group.length; i++){
            if(group[i] == -1){
                group[i] = m;
                m++;
            }
        }
        //2. initiate item group 邻接表
        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for(int i = 0; i < m; i ++){
            groupAdj[i] = new ArrayList<>();
        }
        for(int i = 0; i < n; i ++){
            itemAdj[i] = new ArrayList<>();
        }

        //3. draw graph and indgree 数组
        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        for(int i = 0; i < group.length; i++){
            int curGroup = group[i];
            for(int beforeItem: beforeItems.get(i)){
                int beforeGroup = group[beforeItem];
                if(beforeGroup != curGroup){
                    groupAdj[beforeGroup].add(curGroup);
                    groupsIndegree[curGroup]++;
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(Integer item : beforeItems.get(i)){
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        List<Integer> groupList = topologicalSort(groupAdj, groupsIndegree, m);
        if(groupList.size() == 0){
            return new int[0];
        }
        List<Integer> itemList = topologicalSort(itemAdj, itemsIndegree, n);
        if(itemList.size() == 0){
            return new int[0];
        }

        Map<Integer, List<Integer>> group2Items = new HashMap<>();
        for(Integer item : itemList){
            group2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        List<Integer> res = new ArrayList<>();
        for(Integer groupId : groupList){
            List<Integer> items = group2Items.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items); 
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }             

    private List<Integer> topologicalSort(List<Integer>[] adj, int[] indegree, int n){
        List<Integer> res = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < n; i++){
            if(indegree[i] == 0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            Integer front = q.poll();
            res.add(front);
            for(int successer : adj[front]){
                indegree[successer]--;
                if(indegree[successer] == 0){
                    q.offer(successer);
                }
            }
        }

        if(res.size() == n){
            return res;
        }
        return new ArrayList<>();
    }
}

复杂度分析

• 时间复杂度：O(m+n^2)
• 空间复杂度：O(M+N^2)

[zwmanman]

这题太难了，做了另外一到拓扑排序，熟练之后再来刷这题

207. Course Schedule class Solution(object): def canFinish(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: bool """ indegree = [0] * numCourses dependCourse = [[] for i in range(numCourses) ]

     for fr, to in prerequisites:
         indegree[to] += 1
         dependCourse[fr].append(to)
     
     queue = []
     count = 0
     
     for idx, degree in enumerate(indegree):
         if degree == 0:
             queue.append(idx)
             count += 1
     
     while queue:
         course = queue.pop(0)
         for n_course in dependCourse[course]:
             indegree[n_course] -= 1
             if indegree[n_course] == 0:
                 queue.append(n_course)
                 count += 1
     
     return count == numCourses

[Serena9]

代码

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:

            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

[zol013]

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)

        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)
        return ans

    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = defaultdict(int)
        group_indegree = defaultdict(int)
        project_neighbors = defaultdict(list)
        group_neighbors = defaultdict(list)
        group_projects = defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for preitem in beforeItems[project]:
                if group[preitem] != group[project]:
                    group_indegree[group[project]] += 1
                    group_neighbors[group[preitem]].append(group[project])
                else:
                    project_indegree[project] += 1
                    project_neighbors[preitem].append(project)

        ans = []

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:
            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)
            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans  += project_queue

        return ans

[Okkband]

class Solution {
public:
    vector<int> topSort(vector<int>& deg, vector<vector<int>>& graph, vector<int>& items) {
        queue<int> Q;
        for (auto& item: items) {
            if (deg[item] == 0) {
                Q.push(item);
            }
        }
        vector<int> res;
        while (!Q.empty()) {
            int u = Q.front(); 
            Q.pop();
            res.emplace_back(u);
            for (auto& v: graph[u]) {
                if (--deg[v] == 0) {
                    Q.push(v);
                }
            }
        }
        return res.size() == items.size() ? res : vector<int>{};
    }

    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupItem(n + m);

        // 组间和组内依赖图
        vector<vector<int>> groupGraph(n + m);
        vector<vector<int>> itemGraph(n);

        // 组间和组内入度数组
        vector<int> groupDegree(n + m, 0);
        vector<int> itemDegree(n, 0);

        vector<int> id;
        for (int i = 0; i < n + m; ++i) {
            id.emplace_back(i);
        }

        int leftId = m;
        // 给未分配的 item 分配一个 groupId
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem[group[i]].emplace_back(i);
        }
        // 依赖关系建图
        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (auto& item: beforeItems[i]) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    itemDegree[i] += 1;
                    itemGraph[item].emplace_back(i);   
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph[beforeGroupId].emplace_back(curGroupId);
                }
            }
        }

        // 组间拓扑关系排序
        vector<int> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0) {
            return vector<int>{};
        } 
        vector<int> ans;
        // 组内拓扑关系排序
        for (auto& curGroupId: groupTopSort) {
            int size = groupItem[curGroupId].size();
            if (size == 0) {
                continue;
            }
            vector<int> res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
            if (res.size() == 0) {
                return vector<int>{};
            }
            for (auto& item: res) {
                ans.emplace_back(item);
            }
        }
        return ans;
    }
};

[Yachen-Guo]

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:

            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

[wenlong201807]

代码块

var sortItems = function (n, m, group, beforeItems) {
  const grahG = [],
    degG = new Uint16Array(n + m),
    idsG = [],
    grahI = [],
    degI = new Uint16Array(n),
    idsI = [],
    r = [];
  for (let i = 0; i < n; i++) {
    if (group[i] === -1) {
      idsG[m] = m; // 从组数起分配，避免重复
      group[i] = m++;
    } else idsG[group[i]] = group[i];
    if (!idsI[group[i]]) idsI[group[i]] = []; // 同组项目，放入到一起
    idsI[group[i]].push(i);
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < beforeItems[i].length; j++) {
      const itemI = beforeItems[i][j];
      if (group[i] === group[itemI]) {
        // 同组，收集 项目 依赖
        degI[i]++;
        if (!grahI[itemI]) grahI[itemI] = [];
        grahI[itemI].push(i);
      } else {
        // 不同组，收集 组 依赖
        degG[group[i]]++;
        if (!grahG[group[itemI]]) grahG[group[itemI]] = [];
        grahG[group[itemI]].push(group[i]);
      }
    }
  }
  const idsGS = sort(
    idsG.filter((v) => v !== void 0),
    grahG,
    degG
  ); // 组排序
  if (idsGS.length === 0) return [];
  for (let i = 0; i < idsGS.length; i++) {
    // 组有序，组内项目排序
    if (!idsI[idsGS[i]]) continue;
    const idsIS = sort(idsI[idsGS[i]], grahI, degI);
    if (idsIS.length === 0) return [];
    r.push(...idsIS);
  }
  return r;
};
const sort = (ids, grah, deg) => {
  // 拓扑排序：id列表，图，入度
  const q = [],
    r = [];
  let start = 0;
  for (let i = 0; i < ids.length; i++) if (deg[ids[i]] === 0) q.push(ids[i]);
  while (start < q.length) {
    const n = q[start++];
    r.push(n);
    if (!grah[n]) continue;
    for (let i = 0; i < grah[n].length; i++)
      if (--deg[grah[n][i]] === 0) q.push(grah[n][i]);
  }
  return r.length === ids.length ? r : [];
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[xiao-xiao-meng-xiang-jia]

public class Solution { public int[] sortItems(int n, int m, int[] group, List<List> beforeItems) { // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号 for (int i = 0; i < group.length; i++) { if (group[i] == -1) { group[i] = m; m++; } }

    // 第 2 步：实例化组和项目的邻接表
    List<Integer>[] groupAdj = new ArrayList[m];
    List<Integer>[] itemAdj = new ArrayList[n];
    for (int i = 0; i < m; i++) {
        groupAdj[i] = new ArrayList<>();
    }
    for (int i = 0; i < n; i++) {
        itemAdj[i] = new ArrayList<>();
    }

    // 第 3 步：建图和统计入度数组
    int[] groupsIndegree = new int[m];
    int[] itemsIndegree = new int[n];

    int len = group.length;
    for (int i = 0; i < len; i++) {
        int currentGroup = group[i];
        for (int beforeItem : beforeItems.get(i)) {
            int beforeGroup = group[beforeItem];
            if (beforeGroup != currentGroup) {
                groupAdj[beforeGroup].add(currentGroup);
                groupsIndegree[currentGroup]++;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (Integer item : beforeItems.get(i)) {
            itemAdj[item].add(i);
            itemsIndegree[i]++;
        }
    }

    // 第 4 步：得到组和项目的拓扑排序结果
    List<Integer> groupsList = topologicalSort(groupAdj, groupsIndegree, m);
    if (groupsList.size() == 0) {
        return new int[0];
    }
    List<Integer> itemsList = topologicalSort(itemAdj, itemsIndegree, n);
    if (itemsList.size() == 0) {
        return new int[0];
    }

    // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
    // key：组，value：在同一组的项目列表
    Map<Integer, List<Integer>> groups2Items = new HashMap<>();
    for (Integer item : itemsList) {
        groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
    }

    // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
    List<Integer> res = new ArrayList<>();
    for (Integer groupId : groupsList) {
        List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
        res.addAll(items);
    }
    return res.stream().mapToInt(Integer::valueOf).toArray();
}

private List<Integer> topologicalSort(List<Integer>[] adj, int[] inDegree, int n) {
    List<Integer> res = new ArrayList<>();
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    while (!queue.isEmpty()) {
        Integer front = queue.poll();
        res.add(front);
        for (int successor : adj[front]) {
            inDegree[successor]--;
            if (inDegree[successor] == 0) {
                queue.offer(successor);
            }
        }
    }

    if (res.size() == n) {
        return res;
    }
    return new ArrayList<>();
}

}

[phybrain]

思路

拓扑排序

代码

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:

            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

复杂度分析

• 时间复杂度：O(N)，
• 空间复杂度：O(N)

[tongxw]

思路

1. 把没人管的项目，分配到一个新的组
2. 哈希表统计每个组要负责的项目，只有同一组的项目才有先后顺序
3. 根据项目的先后顺序，可以分别建立组和项目的DAG

4. 先对组拓扑排序，再对组里的项目拓扑排序

   class Solution {
   public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
       Map<Integer, List<Integer>> groupToItems = new HashMap<>();
       int newGroup = m;
       for (int item=0; item<n; item++) {
           if (group[item] == -1) {
               // 没人管的项目分配一个新的组
               group[item] = newGroup++;
           }
   
           // groupId -> [item1, item2, ...]
           groupToItems.computeIfAbsent(group[item], k -> new ArrayList<>()).add(item);
       }
   
       List<Integer>[] groupGraph = new List[newGroup];
       List<Integer>[] itemGraph = new List[n];
       List<Integer> groupIds = new ArrayList<>();
       for (int i=0; i<newGroup; i++) {
           groupGraph[i] = new ArrayList<>();
           groupIds.add(i);
       }
       for (int i=0; i<n; i++) {
           itemGraph[i] = new ArrayList<>();
       }
   
       int[] groupInDegrees = new int[newGroup];
       int[] itemInDegrees = new int[n];
       for (int item=0; item<beforeItems.size(); item++) {
           int groupId = group[item];
           for (int beforeItem : beforeItems.get(item)) {
               int beforeGroupId = group[beforeItem];
               if (beforeGroupId != groupId) {
                   // 不同的组，根据项目确定组和组之间的依赖关系
                   // beforeGroupId -> groupId
                   groupGraph[beforeGroupId].add(groupId);
                   groupInDegrees[groupId]++;
               } else {
                   // 相同的组，记录项目的依赖关系
                   // beforeItem -> item
                   itemGraph[beforeItem].add(item);
                   itemInDegrees[item]++;
               }
   
           }
       }
   
       // 对组拓扑排序
       List<Integer> sortGroups = topSort(groupGraph, groupInDegrees, groupIds);
       if (sortGroups.isEmpty()) {
           return new int[0];
       }
   
       int[] ans = new int[n];
       int idx = 0;
       for (int groupId: sortGroups) {
           // 组内再对项目拓扑排序
           List<Integer> items = groupToItems.getOrDefault(groupId, new ArrayList<>());
           if (items.isEmpty()) {
               continue;
           }
   
           List<Integer> sortItems = topSort(itemGraph, itemInDegrees, items);
           if (sortItems.isEmpty()) {
               return new int[0];
           }
   
           for (int item : sortItems) {
               ans[idx++] = item;
           }
       }
   
       return ans;
   }
   
   private List<Integer> topSort(List<Integer>[] graph, int[] indegrees, List<Integer> items) {
       List<Integer> result = new ArrayList<>();
       Queue<Integer> q = new LinkedList<>();
       for (int item : items) {
           if (indegrees[item] == 0) {
               q.offer(item);
           }
       }
   
       while (!q.isEmpty()) {
           int cur = q.poll();
           result.add(cur);
           for (int neibor : graph[cur]) {
               indegrees[neibor]--;
               if (indegrees[neibor] == 0) {
                   q.offer(neibor);
               }
           }
       }
   
       return result.size() == items.size() ? result : new ArrayList<>();
   }
   }

   TC: O(V+ E) SC: O(V)

[ginnydyy]

Problem

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

Notes

• Use topological sort.
• The problem is about dependent items, can think of using topological sort as a solution.
• Need to sort the groups and items respectively in topo order, and based on the groups' topo order, output the items of each group also in topo order.
• Since some items do not belong to any group (thus -1th group), need to rearrange new group IDs to these items.
• In topo sort method, need to check whether the result size is the same as the indegree length, which means all the items can be sort in topo order. If not, return empty result, otherwise, return the sorted result.
• Having the groups and items topo order lists, have to build a group to items map as per the groups' topo order as the keys and the items' topo order in the list as the value for each group. Cannot use embedded two for loops to output the items into the result, because there will be two test cases in Leetcode that result in TLE.
• Based on the group to items map, iterate the groups in the groups' topo order, and put all the items of each group into the result.

Solution

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // preprocessing - assign new group id to the -1th groups
        for(int i = 0; i < n; i++){
            if(group[i] == -1){
                group[i] = m;
                m++;
            }
        }

        // build the group and item adjacent lists and indegree arrays
        // to make sure all the groups and items have corresponding list in the map, initiate with empty list first
        Map<Integer, List<Integer>> groupAdjacentList = new HashMap<>();
        for(int i = 0; i < m; i++){
            groupAdjacentList.put(i, new ArrayList<>());
        }
        Map<Integer, List<Integer>> itemAdjacentList = new HashMap<>();
        for(int i = 0; i < n; i++){
            itemAdjacentList.put(i, new ArrayList<>());
        }
        int[] groupIndegree = new int[m];
        int[] itemIndegree = new int[n];

        for(int i = 0; i < n; i++){ // iterate all the items and build the adjacent list and indegree array
            int currentGroup = group[i];
            for(int dependentItem: beforeItems.get(i)){
                // item
                itemAdjacentList.get(dependentItem).add(i);
                itemIndegree[i]++;

                // group
                int dependentGroup = group[dependentItem];
                if(dependentGroup != currentGroup){ // avoid putting duplicate groups in the adjacent list
                    groupAdjacentList.get(dependentGroup).add(currentGroup);
                    groupIndegree[currentGroup]++;
                }
            }
        }

        // sort the groups and items in topo order
        // if the groups or items cannot be sorted in topological order, then no solution, return empty array
        List<Integer> groupTopoList = topoSort(groupAdjacentList, groupIndegree);
        if(groupTopoList.size() == 0){
            return new int[0];
        }

        List<Integer> itemTopoList = topoSort(itemAdjacentList, itemIndegree);
        if(itemTopoList.size() == 0){
            return new int[0];
        }

        // group the items in topo order as per their groups
        Map<Integer, List<Integer>> groupMap = new HashMap<>();
        for(int i = 0; i < n; i++){
            int item = itemTopoList.get(i);
            int groupId = group[item];
            if(!groupMap.containsKey(groupId)){
                groupMap.put(groupId, new ArrayList<>());
            }
            groupMap.get(groupId).add(item);
        }

        // As per group topo order, put the items in each group to the result array
        int[] result = new int[n];
        int index = 0;
        for(int i = 0; i < m; i++){
            int groupId = groupTopoList.get(i);
            if(!groupMap.containsKey(groupId)){
                continue;
            }
            for(int item: groupMap.get(groupId)){
                result[index] = item;
                index++;
            }
        }

        return result;
    }

    private List<Integer> topoSort(Map<Integer, List<Integer>> adjacentList, int[] indegree){
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < indegree.length; i++){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }

        while(!queue.isEmpty()){
            int item = queue.poll();
            result.add(item);
            for(int nextItem: adjacentList.get(item)){
                indegree[nextItem]--;
                if(indegree[nextItem] == 0){
                    queue.offer(nextItem);
                }
            }
        }

        // if result size doesn't equal to the number of items
        // it means the items cannot be sorted in topo order
        if(result.size() != indegree.length){
            return new ArrayList<>();
        }

        return result;
    }
}

Complexity

• Time: O(V + E) for topological sorting. V is the number of vertices. E is the number of edges between the vertices. Worst case each item could belong to one group, and each item depends on other n - 1 items. V == n == m. E == n^2 == m^2.
• Space: O(V + E) for topological sorting to use the adjacent list and indegree array. Worst case each item belongs to one group, each item depends to other n - 1 items. The adjacent list hash map has n keys and n - 1 values for each key, so the size is n^2.

[charlestang]

思路

一看题目是项目的前后依赖关系，我就发现了这是一个拓扑排序，就是一下在没想明白，项目属于 group 是怎么个概念。 后来看了题解，才发现，因为项目的前后依赖关系，而项目又属于 group，所以使得 group 也有了前后依赖的关系。

这样就，题目就成了双重的拓扑排序的概念。首先项目有前后依赖，其次，组也有前后依赖。将组和项目分别拓扑排序后， 按照组的顺序输出项目的顺序，就得到了题目的解。

代码

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:

        # 数据预处理
        for i in range(n):
            if group[i] == -1:
                group[i] = m
                m += 1

        itemGraph = defaultdict(list)
        itemIndegree = [0] * n
        groupGraph = defaultdict(list)
        groupIndegree = [0] * m

        # 对 group 建图，并统计入度
        for i in range(n):
            currGroup = group[i]
            for item in beforeItems[i]:
                depGroup = group[item]
                if depGroup != currGroup:
                    groupGraph[depGroup].append(currGroup)
                    groupIndegree[currGroup] += 1

        # 对 item 建图，并统计入度
        for i in range(n):
            for item in beforeItems[i]:
                itemGraph[item].append(i)
                itemIndegree[i] += 1

        # 拓扑排序
        def topologicalSort(graph: defaultdict[list], indegree: List[int], cnt: int) -> List[int]:
            q = deque([i for i in range(cnt) if indegree[i] == 0])
            ans = []
            while q:
                node = q.popleft()
                ans.append(node)
                for v in graph[node]:
                    indegree[v] -= 1
                    if indegree[v] == 0:
                        q.append(v)
            if len(ans) == cnt:
                return ans
            return []
        items = topologicalSort(itemGraph, itemIndegree, n)
        groups = topologicalSort(groupGraph, groupIndegree, m)

        if not items or not groups:
            return []

        mapping = defaultdict(list)
        for item in items:
            mapping[group[item]].append(item)

        ans = []
        for g in groups:
            ans += mapping[g]

        return ans

时间复杂度 O(m + n^2 + Eitem + Egroup)

空间复杂度 O(m + n^2)

[last-Battle]

代码

这题不会，研究了一天还是迷迷糊糊的，太难了！

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        //ans保存最后的答案，blank用于返回空数组         
        vector<int> ans,blank;

        //如果某个项目不属于当前任何小组，新建一个小组，并且把它分给这个小组，为了避免冲突，新的小组编号从m开始
        for(int i = 0; i < group.size(); i++)
        if(group[i] == -1)
        {
            group[i] = m++;
        }

        //分别保存组间依赖关系、项目之间的依赖关系、各个小组负责的项目
        vector<int> topoGroup[m],topoItem[n],groupItem[m];
        //分别保存小组和项目在图中的入度
        int groupDgr[m], itemDgr[n];
        //避免添加多余的有向边，依赖关系只需要一条有向边就可以表示
        unordered_set<int> vis;
        memset(groupDgr, 0, sizeof groupDgr);
        memset(itemDgr, 0 ,sizeof itemDgr);
        for(int i = 0; i < beforeItems.size(); i++)
        {
            //将项目添加到对应的组内
            groupItem[group[i]].push_back(i);
            for(int j = 0; j < beforeItems[i].size(); j++)
            {
                //hashval用于判断是否有重复的邮箱边出现
                int u = beforeItems[i][j], hashval = group[u] * m + group[i];
                topoItem[u].push_back(i);
                itemDgr[i]++;
                //自己不能依赖自己
                if(group[i] == group[u] || vis.find(hashval) != vis.end()) continue;
                vis.insert(hashval);
                topoGroup[group[u]].push_back(group[i]);
                groupDgr[group[i]]++;
            }
        }

        //groupOrder保存了组的顺序
        vector<int> groupOrder;
        queue<int> q;
        for(int i = 0; i < m; i++)
        if(groupDgr[i] == 0) q.push(i);

        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            groupOrder.push_back(u);
            for(int i = 0; i < topoGroup[u].size(); i++)
            {
                int v = topoGroup[u][i];
                groupDgr[v]--;
                if(groupDgr[v] == 0) q.push(v);
            }
        }

        //判断组内项目是否满足拓扑排序
        for(int i = 0; i < groupOrder.size(); i++)
        {
            int t = groupOrder[i];
            for(int j = 0; j < groupItem[t].size(); j++)
            {
                int u = groupItem[t][j];
                if(itemDgr[u] == 0) q.push(u);
            }

            int cnt = 0;
            while(!q.empty())
            {
                int u = q.front();
                q.pop();
                cnt++;
                ans.push_back(u);
                for(int j = 0; j < topoItem[u].size(); j++)
                {
                    int v = topoItem[u][j];
                    itemDgr[v]--;
                    if(itemDgr[v] == 0 && group[v] == t) q.push(v);
                }
            }
            if(cnt != groupItem[t].size()) return blank;
        }

        //如果组间关系不能满足拓扑排序，必定有项目不能加入ans内
        if(ans.size() != n) return blank;

        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[tangjy149]

代码

class Solution {
public:
    using UMIV = unordered_map<int, vector<int> >;
    using UMII = unordered_map<int, int>;
    using VVI = vector<vector<int> >;
    using VI = vector<int>;

    UMIV sub;
    // n个项目， m个小组
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& befores) {
        for (int j = 0; j < n; j++) {
            if (group[j] == -1){
                group[j] = m++;
            }
        }

        // 保存一个小组里有哪些任务，拓扑排序前
        vector<vector<int> > gg(m);
        for (int j = 0; j < n; j++){
            gg[group[j]].push_back(j);
        }

        // 按项目拓扑
        for (int i = 0; i < gg.size(); i++) {
            if (gg[i].size() == 1) {
                int itemId = gg[i][0];
                sub[group[itemId]]= {itemId};
                continue;
            }
            bool f = topoSort(i, gg[i], befores);
            if (f == false) return {};
        }

        // 按小组拓扑
        VI groups; 
        for (int i = 0; i < m; i++){
             groups.push_back(i);
        }
        VVI newbefore(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < befores[i].size(); j++) {
                int prevId = group[befores[i][j]];
                if (prevId != group[i]) newbefore[group[i]].push_back(prevId);
            }
        }
        if(!topoSort(m, groups, newbefore)) return {};
        VI rs;
        for (auto v : sub[m]){
            rs.insert(rs.end(), sub[v].begin(), sub[v].end());
        }
        return rs;
    }

    bool topoSort(int gpid, VI& num, VVI& bef) {
        int n = num.size();
        UMII degree; // 度
        UMIV g; // 图
        for (int i = 0; i < n; i++) {
            degree[num[i]] = 0;
            g[num[i]] = vector<int>();
        }
        // 计算每个节点的入度
        for (int i = 0; i < n; i++) {
            int idx = num[i];
            if(bef[idx].size() == 0) continue;
            for (int j = 0; j < bef[idx].size(); j++) {
                int last = bef[idx][j];
                if (degree.find(last) == degree.end()) continue;
                g[last].push_back(idx);
                degree[idx]++;
            }
        }
        VI res;
        queue<int> q;
        // 入度为0的节点加入队列
        for (int i = 0; i < n; i++) {
            if (degree[num[i]] == 0) 
                q.push(num[i]);
        }
        // 排序
        while (!q.empty()) {
            int cur = q.front();
            res.push_back(cur);
            if (g[cur].size() != 0) {
                for (int i = 0; i < g[cur].size(); i++) {
                    if (--degree[g[cur][i]] == 0) q.push(g[cur][i]);
                }
            }
            q.pop();
        }
        // 将排序好的结果加入到sub中
        sub[gpid] = move(res);
        return sub[gpid].size() == n;
    }
};

[JudyZhou95]

代码

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:

            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

[alongchong]

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Solution {

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // 第 1 步：数据预处理，给没有归属于一个组的项目编上组号
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }

        // 第 2 步：实例化组和项目的邻接表
        List<Integer>[] groupAdj = new ArrayList[m];
        List<Integer>[] itemAdj = new ArrayList[n];
        for (int i = 0; i < m; i++) {
            groupAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            itemAdj[i] = new ArrayList<>();
        }

        // 第 3 步：建图和统计入度数组
        int[] groupsIndegree = new int[m];
        int[] itemsIndegree = new int[n];

        int len = group.length;
        for (int i = 0; i < len; i++) {
            int currentGroup = group[i];
            for (int beforeItem : beforeItems.get(i)) {
                int beforeGroup = group[beforeItem];
                if (beforeGroup != currentGroup) {
                    groupAdj[beforeGroup].add(currentGroup);
                    groupsIndegree[currentGroup]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (Integer item : beforeItems.get(i)) {
                itemAdj[item].add(i);
                itemsIndegree[i]++;
            }
        }

        // 第 4 步：得到组和项目的拓扑排序结果
        List<Integer> groupsList = topologicalSort(groupAdj, groupsIndegree, m);
        if (groupsList.size() == 0) {
            return new int[0];
        }
        List<Integer> itemsList = topologicalSort(itemAdj, itemsIndegree, n);
        if (itemsList.size() == 0) {
            return new int[0];
        }

        // 第 5 步：根据项目的拓扑排序结果，项目到组的多对一关系，建立组到项目的一对多关系
        // key：组，value：在同一组的项目列表
        Map<Integer, List<Integer>> groups2Items = new HashMap<>();
        for (Integer item : itemsList) {
            groups2Items.computeIfAbsent(group[item], key -> new ArrayList<>()).add(item);
        }

        // 第 6 步：把组的拓扑排序结果替换成为项目的拓扑排序结果
        List<Integer> res = new ArrayList<>();
        for (Integer groupId : groupsList) {
            List<Integer> items = groups2Items.getOrDefault(groupId, new ArrayList<>());
            res.addAll(items);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    private List<Integer> topologicalSort(List<Integer>[] adj, int[] inDegree, int n) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer front = queue.poll();
            res.add(front);
            for (int successor : adj[front]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) {
                    queue.offer(successor);
                }
            }
        }

        if (res.size() == n) {
            return res;
        }
        return new ArrayList<>();
    }
}

[junbuer]

思路

• 双层拓扑排序
  • 先对小组根据依赖性进行拓扑排序
  • 再对每个小组负责的项目进行拓扑排序
  • 将排序好的项目依次放入ans中

代码

class Solution(object):
    # 拓扑排序
    def top_sort(self, items, indegree, neighbors):
        que = deque([i for i in items if indegree[i] == 0])
        ans = []
        while que:
            cur = que.popleft()
            ans.append(cur)
            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    que.append(neighbor)
        return ans
    def sortItems(self, n, m, group, beforeItems):
        """
        :type n: int
        :type m: int
        :type group: List[int]
        :type beforeItems: List[List[int]]
        :rtype: List[int]
        """
        # 无人负责的项目重新编号从 m 开始
        max_id = m
        for item in range(n):
            if group[item] == -1:
                group[item] = max_id 
                max_id += 1

        group_item = defaultdict(list)
        item_indegree = defaultdict(int)
        item_neighbors = defaultdict(list)
        group_indegree = defaultdict(int)
        group_neighbors = defaultdict(list)

        for item in range(n):
            # 小组和项目间的一对多关系
            group_item[group[item]].append(item) # group[item]负责当前项目的小组

            for pre in beforeItems[item]:
                # 判断当前项目的依赖项是否由当前小组负责

                # 小组间依赖关系
                if group[pre] != group[item]: 
                    group_indegree[group[item]] += 1
                    group_neighbors[group[pre]].append(group[item])

                # 项目的依赖关系
                else:
                    item_indegree[item] += 1
                    item_neighbors[pre].append(item)

        # 分级排序返回答案
        ans = []
        # 小组根据依赖关系排序
        group_que = self.top_sort([i for i in range(max_id)], group_indegree, group_neighbors)
        if len(group_que) != max_id:
            return []
        # 给小组负责的项目根据依赖关系排序
        for group_id in group_que:
            item_que = self.top_sort(group_item[group_id], item_indegree, item_neighbors) 
            if len(item_que) != len(group_item[group_id]):
                return []
            ans += item_que
        return ans

复杂度分析

• 时间复杂度：$O(n + m)$
• 空间复杂度：$O(n + m)$

[machuangmr]

代码

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        List<List<Integer>> groupItem = new ArrayList<List<Integer>>();
        for (int i = 0; i < n + m; ++i) {
            groupItem.add(new ArrayList<Integer>());
        }

        // 组间和组内依赖图
        List<List<Integer>> groupGraph = new ArrayList<List<Integer>>();
        for (int i = 0; i < n + m; ++i) {
            groupGraph.add(new ArrayList<Integer>());
        }
        List<List<Integer>> itemGraph = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; ++i) {
            itemGraph.add(new ArrayList<Integer>());
        }

        // 组间和组内入度数组
        int[] groupDegree = new int[n + m];
        int[] itemDegree = new int[n];

        List<Integer> id = new ArrayList<Integer>();
        for (int i = 0; i < n + m; ++i) {
            id.add(i);
        }

        int leftId = m;
        // 给未分配的 item 分配一个 groupId
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem.get(group[i]).add(i);
        }
        // 依赖关系建图
        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (int item : beforeItems.get(i)) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    itemDegree[i] += 1;
                    itemGraph.get(item).add(i);   
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph.get(beforeGroupId).add(curGroupId);
                }
            }
        }

        // 组间拓扑关系排序
        List<Integer> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0) {
            return new int[0];
        }
        int[] ans = new int[n];
        int index = 0;
        // 组内拓扑关系排序
        for (int curGroupId : groupTopSort) {
            int size = groupItem.get(curGroupId).size();
            if (size == 0) {
                continue;
            }
            List<Integer> res = topSort(itemDegree, itemGraph, groupItem.get(curGroupId));
            if (res.size() == 0) {
                return new int[0];
            }
            for (int item : res) {
                ans[index++] = item;
            }
        }
        return ans;
    }

    public List<Integer> topSort(int[] deg, List<List<Integer>> graph, List<Integer> items) {
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int item : items) {
            if (deg[item] == 0) {
                queue.offer(item);
            }
        }
        List<Integer> res = new ArrayList<Integer>();
        while (!queue.isEmpty()) {
            int u = queue.poll(); 
            res.add(u);
            for (int v : graph.get(u)) {
                if (--deg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        return res.size() == items.size() ? res : new ArrayList<Integer>();
    }
}

复杂度

• 时间复杂度 O(n + m)
• 空间复杂度 O(n + m)

[guoling0019]

JavaScript Code:

const topSort = (deg, graph, items) => {
    const Q = [];
    for (const item of items) {
        if (deg[item] === 0) {
            Q.push(item);
        }
    }
    const res = [];
    while (Q.length) {
        const u = Q.shift(); 
        res.push(u);
        for (let i = 0; i < graph[u].length; ++i) {
            const v = graph[u][i];
            if (--deg[v] === 0) {
                Q.push(v);
            }
        }
    }
    return res.length == items.length ? res : [];
}

var sortItems = function(n, m, group, beforeItems) {
    const groupItem = new Array(n + m).fill(0).map(() => []);

    const groupGraph = new Array(n + m).fill(0).map(() => []);
    const itemGraph = new Array(n).fill(0).map(() => []);

    const groupDegree = new Array(n + m).fill(0);
    const itemDegree = new Array(n).fill(0);

    const id = new Array(n + m).fill(0).map((v, index) => index);

    let leftId = m;
    for (let i = 0; i < n; ++i) {
        if (group[i] === -1) {
            group[i] = leftId;
            leftId += 1;
        }
        groupItem[group[i]].push(i);
    }
    for (let i = 0; i < n; ++i) {
        const curGroupId = group[i];
        for (const item of beforeItems[i]) {
            const beforeGroupId = group[item];
            if (beforeGroupId === curGroupId) {
                itemDegree[i] += 1;
                itemGraph[item].push(i);   
            } else {
                groupDegree[curGroupId] += 1;
                groupGraph[beforeGroupId].push(curGroupId);
            }
        }
    }

    const groupTopSort = topSort(groupDegree, groupGraph, id); 
    if (groupTopSort.length == 0) {
        return [];
    } 
    const ans = [];
    for (const curGroupId of groupTopSort) {
        const size = groupItem[curGroupId].length;
        if (size == 0) {
            continue;
        }
        const res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
        if (res.length === 0) {
            return [];
        }
        for (const item of res) {
            ans.push(item);
        }
    }
    return ans;
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[Liuxy94]

思路

不是很会 背题解也背了很久

代码

class Solution:
    def tp_sort(self, items, indegree, neighbors):
        q = collections.deque([])
        ans = []
        for item in items:
            if not indegree[item]:
                q.append(item)
        while q:
            cur = q.popleft()
            ans.append(cur)

            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    q.append(neighbor)

        return ans

    def sortItems(self, n: int, m: int, group: List[int], pres: List[List[int]]) -> List[int]:
        max_group_id = m
        for project in range(n):
            if group[project] == -1:
                group[project] = max_group_id
                max_group_id += 1

        project_indegree = collections.defaultdict(int)
        group_indegree = collections.defaultdict(int)
        project_neighbors = collections.defaultdict(list)
        group_neighbors = collections.defaultdict(list)
        group_projects = collections.defaultdict(list)

        for project in range(n):
            group_projects[group[project]].append(project)

            for pre in pres[project]:
                if group[pre] != group[project]:
                    # 小组关系图
                    group_indegree[group[project]] += 1
                    group_neighbors[group[pre]].append(group[project])
                else:
                    # 项目关系图
                    project_indegree[project] += 1
                    project_neighbors[pre].append(project)

        ans = []

        group_queue = self.tp_sort([i for i in range(max_group_id)], group_indegree, group_neighbors)

        if len(group_queue) != max_group_id:
            return []

        for group_id in group_queue:

            project_queue = self.tp_sort(group_projects[group_id], project_indegree, project_neighbors)

            if len(project_queue) != len(group_projects[group_id]):
                return []
            ans += project_queue

        return ans

复杂度分析

时间复杂度： O(m+n)

空间复杂度：O(m+n)

[Toms-BigData]

func topSort(graph [][]int, deg, items []int) (orders []int) { q := []int{} for , i := range items { if deg[i] == 0 { q = append(q, i) } } for len(q) > 0 { from := q[0] q = q[1:] orders = append(orders, from) for , to := range graph[from] { deg[to]-- if deg[to] == 0 { q = append(q, to) } } } return }

func sortItems(n, m int, group []int, beforeItems [][]int) (ans []int) { groupItems := make([][]int, m+n) // groupItems[i] 表示第 i 个组负责的项目列表 for i := range group { if group[i] == -1 { group[i] = m + i // 给不属于任何组的项目分配一个组 } groupItems[group[i]] = append(groupItems[group[i]], i) }

groupGraph := make([][]int, m+n) // 组间依赖关系
groupDegree := make([]int, m+n)
itemGraph := make([][]int, n) // 组内依赖关系
itemDegree := make([]int, n)
for cur, items := range beforeItems {
    curGroupID := group[cur]
    for _, pre := range items {
        preGroupID := group[pre]
        if preGroupID != curGroupID { // 不同组项目，确定组间依赖关系
            groupGraph[preGroupID] = append(groupGraph[preGroupID], curGroupID)
            groupDegree[curGroupID]++
        } else { // 同组项目，确定组内依赖关系
            itemGraph[pre] = append(itemGraph[pre], cur)
            itemDegree[cur]++
        }
    }
}

// 组间拓扑序
items := make([]int, m+n)
for i := range items {
    items[i] = i
}
groupOrders := topSort(groupGraph, groupDegree, items)
if len(groupOrders) < len(items) {
    return nil
}

// 按照组间的拓扑序，依次求得各个组的组内拓扑序，构成答案
for _, groupID := range groupOrders {
    items := groupItems[groupID]
    orders := topSort(itemGraph, itemDegree, items)
    if len(orders) < len(items) {
        return nil
    }
    ans = append(ans, orders...)
}
return

}

[Macvh]

class Solution: def topological_sort(self,items,indegree,neighbors):

建立队列和访问顺序

    queue = collections.deque()
    res = []

    # 初始化队列
    for item in items:
        if not indegree[item]:
            queue.append(item)

    if not queue: return []

    # BFS
    while queue:
        cur = queue.popleft()
        res.append(cur)

        # 遍历邻居节点
        for neighbor in neighbors[cur]:
            indegree[neighbor] -= 1
            if not indegree[neighbor]:
                queue.append(neighbor)

    return res

def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
    max_group_id = m
    for task in range(n):
        if group[task] == -1:
            group[task] = max_group_id
            max_group_id += 1

    task_indegree = [0] * n    
    group_indegree = [0] * max_group_id
    task_neighbors = [[] for _ in range(n)]
    group_neighbors = [[] for _ in range(max_group_id)]
    group_to_tasks = [[] for _ in range(max_group_id)]

    for task in range(n):
        group_to_tasks[group[task]].append(task)

        for prerequisite in beforeItems[task]:

            # 判断相关联的两个项目是否属于同一组
            if group[prerequisite] != group[task]:

                # 不是同组，给小组建图
                group_indegree[group[task]] += 1
                group_neighbors[group[prerequisite]].append(group[task])
            else:
                # 同组，给组内项目建图
                task_indegree[task] += 1
                task_neighbors[prerequisite].append(task)

    res = []

    # 得到小组的访问顺序
    group_queue = self.topological_sort([i for i in range(max_group_id)],group_indegree,group_neighbors)

    if len(group_queue) != max_group_id: return []

    for group_id in group_queue:
        # 得到每组项目的访问顺序
        task_queue = self.topological_sort(group_to_tasks[group_id],task_indegree,task_neighbors)

        if len(task_queue) != len(group_to_tasks[group_id]):
            return []
        res += task_queue

    return res

[CodeWithIris]

Question

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

Note (Topological sorting)

Solution (C++)

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++; // 把组号为-1的重新编号，从m开始
        }
        vector<vector<int>> itemgraph(n);
        vector<vector<int>> groupgraph(m);
        vector<int> itemIndegree(n, 0);
        vector<int> groupIndegree(m, 0);
        for(int i = 0; i < n; i++)
        {
            for(auto j : beforeItems[i])
            {
                itemgraph[j].push_back(i);//建图
                itemIndegree[i]++;//记录出入度
                if(group[i] != group[j]) // 注意条件
                {   // 团队也建图，记录出入度
                    groupgraph[group[j]].push_back(group[i]);
                    groupIndegree[group[i]]++;
                }
            }
        }
        vector<vector<int>> g_items(m);
        // item 拓扑排序
        queue<int> q;
        for(int i = 0; i < n; i++)
            if(itemIndegree[i] == 0)
                q.push(i);
        int countItem = 0;
        while(!q.empty())
        {
            int i = q.front();
            q.pop();
            countItem++;
            g_items[group[i]].push_back(i);
            //每个item顺序存入自己的团队
            for(auto j : itemgraph[i])
            {
                if(--itemIndegree[j]==0)
                    q.push(j);
            }
        }
        if(countItem != n)
            return {};
        // 团队拓扑排序
        vector<int> g_order;
        for(int i = 0; i < m; i++)
            if(groupIndegree[i] == 0)
                q.push(i);
        int countgroup = 0;
        while(!q.empty())
        {
            int g = q.front();
            q.pop();
            countgroup++;
            g_order.push_back(g);
            for(auto j : groupgraph[g])
            {
                if(--groupIndegree[j]==0)
                    q.push(j);
            }
        }
        if(countgroup != m)
            return {};
        vector<int> ans(n);
        int idx = 0;
        for(auto g : g_order)
        {
            for(auto i : g_items[g])
                ans[idx++] = i;
        }
        return ans;
    }
};

Complexity

• T: O(n + m)
• S: O(n + m)

[KennethAlgol]

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        Map<Integer, Integer> indegreeMap = new HashMap();
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, List<Integer>> groupMap = new HashMap<>();
        Map<Integer, Integer> grpIndegreeMap = new HashMap();
        Map<Integer, List<Integer>> grpGraph = new HashMap<>();

        for (int i = 0; i < n; i++) {
            indegreeMap.put(i, 0);
            graph.put(i, new ArrayList<>());
        }

        int nextGrpId = m;
        for (int i = 0; i < group.length; i++) {
            if (group[i] == -1) {
                group[i] = nextGrpId;
                nextGrpId++;
            }
            if (groupMap.get(group[i]) == null) {
                groupMap.put(group[i], new ArrayList<>());
            }
            groupMap.get(group[i]).add(i);
        }

        for (int i = 0; i < n; i++) {
            List<Integer> beforeList = beforeItems.get(i);
            if (beforeList != null) {
                for (Integer id : beforeList) {
                    if (group[i] == group[id]) {
                        indegreeMap.put(i, indegreeMap.get(i) + 1);
                        graph.get(id).add(i);
                    }
                }
            }
        }

        Map<Integer, List<Integer>> sortedGroupItemMap = new HashMap<>();
        for (int grpId : groupMap.keySet()) {
            List<Integer> sortedGroupItem = topoLogicSort(groupMap.get(grpId), indegreeMap, graph);
            if (sortedGroupItem.size() == 0) {
                return new int[0];
            }
            sortedGroupItemMap.put(grpId, sortedGroupItem);
        }

        for (int grpId : group) {
            grpIndegreeMap.put(grpId, 0);
        }

        for (int i = 0; i < n; i++) {
            List<Integer> beforeList = beforeItems.get(i);
            if (beforeList != null) {
                for (Integer id : beforeList) {
                    if (group[i] != group[id]) {
                        grpIndegreeMap.put(group[i], grpIndegreeMap.getOrDefault(group[i], 0) + 1);
                        if (grpGraph.get(group[id]) == null) {
                            grpGraph.put(group[id], new ArrayList<>());
                        }
                        grpGraph.get(group[id]).add(group[i]);
                    }
                }
            }
        }
        List<Integer> grpIDs = new ArrayList<>(grpIndegreeMap.keySet());
        List<Integer> sortedGrp = topoLogicSort(grpIDs, grpIndegreeMap, grpGraph);
        List<Integer> tempList = new ArrayList<>();
        for (int grpId : sortedGrp) {
            tempList.addAll(sortedGroupItemMap.get(grpId));
        }
        int[] res = new int[tempList.size()];
        for (int i = 0; i < tempList.size(); i++) {
            res[i] = tempList.get(i);
        }
        return res;
    }

    private List<Integer> topoLogicSort(List<Integer> items, Map<Integer, Integer> indegreeMap, Map<Integer, List<Integer>> graph) {
        Queue<Integer> q = new LinkedList<>();
        for (int id : items) {
            if (indegreeMap.get(id) == 0) {
                q.add(id);
            }
        }
        List<Integer> tempList = new ArrayList<>();

        while (!q.isEmpty()) {
            int curId = q.poll();
            tempList.add(curId);
            List<Integer> nextIDs = graph.get(curId);
            if (nextIDs != null) {
                for (Integer nextID : nextIDs) {
                    indegreeMap.put(nextID, indegreeMap.get(nextID) - 1);
                    if (indegreeMap.get(nextID) == 0) {
                        q.add(nextID);
                    }
                }
            }
        }
        if (tempList.size() != items.size()) {
            return new ArrayList<>();
        }
        return tempList;
    }
}

[baddate]

思路：

拓扑排序

代码：

class Solution {
private:
    unordered_map<int, vector<int>> GroupToTask;  //保存每个小组拓扑排序后的任务顺序
    bool topoSort(int groupId, vector<int>& items, vector<vector<int>>& before) { //小组id，小组内所有任务,项目关系
        int n = items.size();
        unordered_map<int, int> inDegrees; // 入度，因为只关心items中元素的邻接关系，无需关心其他其他任务id，因此不必vec(n)
        map<int, set<int>> adj; //邻接图
        vector<int> arrangement;  //拓扑排序后，本小组的任务顺序安排结果
        queue<int> que;  //入度为0的队列
        for (auto& item : items) inDegrees[item] = 0;  //入度表插入本小组内所有的任务，且初始化入度为0
        for (auto& item : items) {  //遍历组内每个task
            if (before[item].size() == 0) continue;  //说明该task没有前置任务
            unordered_set<int> preCondition;  //去除重复的前置条件
            for (auto& preTask : before[item]) {  //该task存在前置任务
                if (!inDegrees.count(preTask)) continue;  //说明当前的前置任务不在当前小组中，不受控
                if (preCondition.count(preTask)) continue;
                else preCondition.insert(preTask);
                inDegrees[item]++;  //当前task入度+1
                adj[preTask].insert(item);  //更新邻接关系表
            }
        }
        for (auto& item : items) {  //遍历当前小组内所有的任务
            if (inDegrees[item] == 0) que.push(item); //入度为0的任务加入队列
        }
        while (!que.empty()) {
            int cur = que.front(); que.pop();
            arrangement.push_back(cur);
            for (auto& next : adj[cur]) {
                inDegrees[next]--;
                if (inDegrees[next] == 0) que.push(next);
            }
        }
        GroupToTask[groupId] = arrangement;  //放入组内任务排序完成后的结果
        return arrangement.size() == n;  //安排前后，任务数量应一致
    }
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& befores) {
        // 如果任务不属于任何小组，说明该任务可以独属一组，给该任务新建一个虚拟组
        for (int j = 0; j < n; j++) if (group[j] == -1) group[j] = m++;  //把组号为-1的重新编号，从m开始
        vector<vector<int>> taskInGroup(m);  //保存一个小组里有哪些任务
        for (int j = 0; j < n; j++) taskInGroup[group[j]].push_back(j);
        for (int i = 0; i < taskInGroup.size(); i++) { // 对每个组内的项目进行拓扑排序
            if (taskInGroup[i].size() == 1) {  // 对于组内只有一个任务的小组，直接加入GroupToTask结果集
                int itemId = taskInGroup[i][0];
                GroupToTask[group[itemId]].push_back(itemId);
                continue;
            }
            if (!topoSort(i, taskInGroup[i], befores)) return {};  //存在某个小组内部任务拓扑排序失败
        }
        vector<int> groups; //新的小组编号
        for (int i = 0; i < m; i++) groups.push_back(i);
        vector<vector<int>> beforeGroups(m);  //小组之间的前后继关系
        for (int i = 0; i < n; i++) {  //遍历所有项目
            unordered_set<int> preGroup;
            for (auto& preId : befores[i]) {  //遍历项目i的前置项目
                if (group[i] != group[preId]) {//说明当前项目i所在的小组和项目i的前置任务所在的小组不是同一个
                    if (preGroup.count(group[preId])) continue;  //当前i小组的前置小组preId重复
                    beforeGroups[group[i]].push_back(group[preId]);  //前置项目的小组成为项目i所在小组的前置
                    preGroup.insert(group[preId]);
                }
            }
        }
        //把小组之间的顺序结果存储在GroupToTask[m]中
        if (!topoSort(m, groups, beforeGroups)) return {};  //小组进行拓扑排序失败
        vector<int> res;
        for (auto& GroupId : GroupToTask[m]) {  //按GroupToTask[m]存储的小组顺序取元素逐个加入res
            res.insert(res.end(), GroupToTask[GroupId].begin(), GroupToTask[GroupId].end());
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(n+m)，其中 n 为点数，m 为边数。拓扑排序时间复杂度为 O(n+m)。
• 空间复杂度：O(n+m)

[stackvoid]

思路

看题解才知道怎么玩

代码

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        List<List<Integer>> groupItem = new ArrayList<List<Integer>>();
        for (int i = 0; i < n + m; ++i) {
            groupItem.add(new ArrayList<Integer>());
        }

        // 组间和组内依赖图
        List<List<Integer>> groupGraph = new ArrayList<List<Integer>>();
        for (int i = 0; i < n + m; ++i) {
            groupGraph.add(new ArrayList<Integer>());
        }
        List<List<Integer>> itemGraph = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; ++i) {
            itemGraph.add(new ArrayList<Integer>());
        }

        // 组间和组内入度数组
        int[] groupDegree = new int[n + m];
        int[] itemDegree = new int[n];

        List<Integer> id = new ArrayList<Integer>();
        for (int i = 0; i < n + m; ++i) {
            id.add(i);
        }

        int leftId = m;
        // 给未分配的 item 分配一个 groupId
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem.get(group[i]).add(i);
        }
        // 依赖关系建图
        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (int item : beforeItems.get(i)) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    itemDegree[i] += 1;
                    itemGraph.get(item).add(i);   
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph.get(beforeGroupId).add(curGroupId);
                }
            }
        }

        // 组间拓扑关系排序
        List<Integer> groupTopSort = topSort(groupDegree, groupGraph, id); 
        if (groupTopSort.size() == 0) {
            return new int[0];
        }
        int[] ans = new int[n];
        int index = 0;
        // 组内拓扑关系排序
        for (int curGroupId : groupTopSort) {
            int size = groupItem.get(curGroupId).size();
            if (size == 0) {
                continue;
            }
            List<Integer> res = topSort(itemDegree, itemGraph, groupItem.get(curGroupId));
            if (res.size() == 0) {
                return new int[0];
            }
            for (int item : res) {
                ans[index++] = item;
            }
        }
        return ans;
    }

    public List<Integer> topSort(int[] deg, List<List<Integer>> graph, List<Integer> items) {
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int item : items) {
            if (deg[item] == 0) {
                queue.offer(item);
            }
        }
        List<Integer> res = new ArrayList<Integer>();
        while (!queue.isEmpty()) {
            int u = queue.poll(); 
            res.add(u);
            for (int v : graph.get(u)) {
                if (--deg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        return res.size() == items.size() ? res : new ArrayList<Integer>();
    }
}

复杂度分析

O(N) O(N)

[uniqlell]

public static int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems)
    {
        // 项目出度
        int[] itemsOut=new int[n];
        // 组出度
        int[] groupOut=new int[m];
        // 键为项目，值为依赖它的项目
        HashMap<Integer,List<Integer>> itemAdj=new HashMap<>();
        // 键为组名，值为该组成员
        HashMap<Integer,List<Integer>> groupMembers=new HashMap<>();

        for (int i = 0; i < beforeItems.size(); i++)
        {
            List<Integer> before = beforeItems.get(i);
            groupMembers.computeIfAbsent(group[i],k->new ArrayList<>()).add(i);

            for (Integer item : before)
            {
                itemsOut[i]++;
                itemAdj.computeIfAbsent(item,k->new ArrayList<>()).add(i);
                // 如果不是-1组，则如果其组内成员对其他组(包括-1组)有依赖，那么组出度+1
                if (group[i]!=-1)
                {
                    // 组内成员之间的依赖要排除
                    if (group[i]!=group[item])
                    {
                        groupOut[group[i]]++;
                    }
                }
            }
        }

        Deque<Integer> deque=new ArrayDeque<>();
        // 按组遍历而不是按项目名称遍历可以防止出度为0的同组成员没有放在一起
        for (int i = -1; i < m; i++)
        {
            // 把出度为0的组内出度为0的项目放进队列，
            if (i==-1||groupOut[i]==0)
            {
                List<Integer> members = groupMembers.get(i);
                // 错点：这里可能有的组无成员导致空指针
                if (members!=null)
                {
                    for (Integer member : members)
                    {
                        if (itemsOut[member] == 0)
                        {
                            deque.addLast(member);
                        }
                    }
                }
            }
        }

        int[] ansr=new int[n];
        int index=0;
        while (!deque.isEmpty())
        {
            Integer cur = deque.removeFirst();
            ansr[index]=cur;
            index++;
            List<Integer> items = itemAdj.get(cur);
            if (items!=null)
            {
                for (Integer item : items)
                {
                    itemsOut[item]--;
                    // 如果对自己有依赖的项目item和自己不同组，就把group[item]的出度-1
                    if (group[item]!=-1&&group[item]!=group[cur])
                    {
                        groupOut[group[item]]--;
                        // 这里很关键，当某一组出度为0（也就是对其他组无依赖）后就要遍历该组找到出度为0的点放进队尾,
                        if (groupOut[group[item]]==0)
                        {
                            for (Integer member : groupMembers.get(group[item]))
                            {
                                if (itemsOut[member]==0)
                                {
                                    deque.addLast(member);
                                }
                            }
                        }
                    }else if (itemsOut[item]==0)
                    {
                        // 这里有两种情况：1：跟自己同组，那么要放在队头才能保证相邻
                        //              2：属于-1组，那么还是放到队尾
                        if (group[cur]==group[item])
                        {
                            deque.addFirst(item);
                        }else
                        {
                            deque.addLast(item);
                        }
                    }
                }
            }
        }

        return index==ansr.length?ansr:new int[]{};
    }

[Hacker90]

思路

看题解-拓扑排序

class Solution {
public:

    vector<int> topSort(vector<int>& in_degree, vector<vector<int>>& g, vector<int>& items){
        queue<int> q;
        for(auto item: items)
            if(in_degree[item]==0) q.push(item);
        vector<int> res;
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            res.push_back(u);
            for(auto v: g[u])
                if(--in_degree[v]==0) q.push(v);
        }
        return (res.size()==items.size())?res:vector<int>{};
    }

    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupitem(n+m);

        vector<vector<int>> groupGraph(n+m);
        vector<vector<int>> itemGraph(n);

        vector<int> group_in_degree(n+m, 0);
        vector<int> item_in_degree(n, 0);

        vector<int> id;
        for(int i=0;i<n+m;i++) id.push_back(i);

        int leftid = m;
        for(int i=0;i<n;i++)
        {
            if(group[i]==-1)
            {
                group[i] = leftid;
                leftid += 1;
            }
            groupitem[group[i]].push_back(i);
        }

        for(int i=0;i<n;i++)
        {
            int cur_groupid = group[i];
            for(auto item: beforeItems[i])
            {
                int before_groupid = group[item];
                if(before_groupid==cur_groupid)
                {
                    item_in_degree[i] += 1;
                    itemGraph[item].push_back(i);
                }
                else
                {
                    group_in_degree[cur_groupid] += 1;
                    groupGraph[before_groupid].push_back(cur_groupid);
                }
            }
        }

        vector<int> groupTopSort = topSort(group_in_degree, groupGraph, id);
        if(groupTopSort.size()==0) return vector<int>{};

        vector<int> ans;
        for(auto cur_groupid: groupTopSort)
        {
            int size = groupitem[cur_groupid].size();
            if(size==0) continue;
            vector<int> res = topSort(item_in_degree, itemGraph, groupitem[cur_groupid]);
            if(res.size()==0) return vector<int>{};
            for(auto item: res) ans.push_back(item);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O()，n为人数
• 空间复杂度：O(n),n为人数

[callmeerika]

思路

太难了，看的题解

代码

const topSort = (deg, graph, items) => {
    const Q = [];
    for (const item of items) {
        if (deg[item] === 0) {
            Q.push(item);
        }
    }
    const res = [];
    while (Q.length) {
        const u = Q.shift(); 
        res.push(u);
        for (let i = 0; i < graph[u].length; ++i) {
            const v = graph[u][i];
            if (--deg[v] === 0) {
                Q.push(v);
            }
        }
    }
    return res.length == items.length ? res : [];
}

var sortItems = function(n, m, group, beforeItems) {
    const groupItem = new Array(n + m).fill(0).map(() => []);

    // 组间和组内依赖图
    const groupGraph = new Array(n + m).fill(0).map(() => []);
    const itemGraph = new Array(n).fill(0).map(() => []);

    // 组间和组内入度数组
    const groupDegree = new Array(n + m).fill(0);
    const itemDegree = new Array(n).fill(0);

    const id = new Array(n + m).fill(0).map((v, index) => index);

    let leftId = m;
    // 给未分配的 item 分配一个 groupId
    for (let i = 0; i < n; ++i) {
        if (group[i] === -1) {
            group[i] = leftId;
            leftId += 1;
        }
        groupItem[group[i]].push(i);
    }
    // 依赖关系建图
    for (let i = 0; i < n; ++i) {
        const curGroupId = group[i];
        for (const item of beforeItems[i]) {
            const beforeGroupId = group[item];
            if (beforeGroupId === curGroupId) {
                itemDegree[i] += 1;
                itemGraph[item].push(i);   
            } else {
                groupDegree[curGroupId] += 1;
                groupGraph[beforeGroupId].push(curGroupId);
            }
        }
    }

    // 组间拓扑关系排序
    const groupTopSort = topSort(groupDegree, groupGraph, id); 
    if (groupTopSort.length == 0) {
        return [];
    } 
    const ans = [];
    // 组内拓扑关系排序
    for (const curGroupId of groupTopSort) {
        const size = groupItem[curGroupId].length;
        if (size == 0) {
            continue;
        }
        const res = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
        if (res.length === 0) {
            return [];
        }
        for (const item of res) {
            ans.push(item);
        }
    }
    return ans;
};

复杂度

时间复杂度：O(n+m)
空间复杂度：O(n+m)