[Swift]LeetCode1203.项目管理|SortItemsbyGroupsRespectingDependencies

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

Return a sorted list of the items such that:

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

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

Example 1:

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

Example 2:

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

Constraints:

1 <= m <= n <= 3*10^4
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]

公司共有 n 个项目和 m 个小组，每个项目要不没有归属，要不就由其中的一个小组负责。

我们用 group[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 的前面。

提示：

1 <= m <= n <= 3*10^4
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]

Runtime: 556 ms

Memory Usage: 28.7 MB

  1 class Solution {
  2     func sortItems(_ n: Int, _ m: Int, _ group: [Int], _ beforeItems: [[Int]]) -> [Int] {
  3         var group = group
  4         var ret:[Int] = [Int]()
  5         //the vector stores the followers of the key which is the group id
  6         var rules_between_groups:[Int:[Int]] = [Int:[Int]]()
  7         //the key is the the group id, the value has similar structure as rules_between_groups
  8         var rules_in_group:[Int:[Int:[Int]]] = [Int:[Int:[Int]]]()
  9         var mm:Int = m
 10         for i in 0..<group.count
 11         {
 12             //asign group ids for the no-group items
 13             if group[i] == -1 {group[i] = mm++}
 14             
 15         }
 16         //parse the following/followed (beforeItems) rules
 17         for i in 0..<beforeItems.count
 18         {
 19             for j in 0..<beforeItems[i].count
 20             {
 21                 if group[beforeItems[i][j]] == group[i]
 22                 {
 23                     let gg:Int = group[i]
 24                     rules_in_group[gg,default:[Int:[Int]]()][beforeItems[i][j],default:[Int]()].append(i)
 25                 }
 26                 else
 27                 {
 28                      rules_between_groups[group[beforeItems[i][j]],default:[Int]()].append(group[i])
 29                 }
 30             }
 31         }
 32         //to remove the duplicated group  id
 33         var groups:Set<Int> = Set<Int>()
 34         //key is the group id, vector stores the items
 35         var items_by_group:[Int:[Int]] = [Int:[Int]]()
 36         for i in 0..<group.count
 37         {
 38             groups.insert(group[i])
 39             items_by_group[group[i],default:[Int]()].append(i)
 40         }
 41         //vector of unique group ids
 42         var vgroup:[Int] = Array(groups)
 43         if !applyRules(&vgroup,&rules_between_groups) {return ret}
 44         for i in 0..<m
 45         {
 46             if !applyRules(&items_by_group[i,default:[Int]()], &rules_in_group[i,default:[Int:[Int]]()])
 47             {
 48                 return ret
 49             }
 50         }
 51         for gg in vgroup
 52         {
 53             for ii in items_by_group[gg,default:[Int]()]
 54             {
 55                 ret.append(ii)
 56             }
 57         }
 58         return ret
 59     }
 60     
 61     func applyRules(_ eles:inout [Int],_ rules:inout [Int:[Int]]) -> Bool
 62     {
 63         //toplogical sort
 64         //id -> indegree number
 65         var indegree:[Int:Int] = [Int:Int]()
 66         for ele in eles
 67         {
 68             indegree[ele] = 0
 69         }
 70         eles.removeAll()
 71         //calculate the indegrees
 72         for valu in rules.values
 73         {
 74             for i in 0..<valu.count
 75             {
 76                 indegree[valu[i],default:0] += 1
 77             }
 78         }
 79         while(indegree.count > 0)
 80         {
 81             let start:Int = eles.count
 82             for (key,val) in indegree
 83             {
 84                 if val == 0
 85                 {
 86                     eles.append(key)
 87                     for aa in rules[key,default:[Int]()]
 88                     {
 89                         indegree[aa,default:0] -= 1
 90                     }
 91                 }
 92             }
 93             let stop:Int = eles.count
 94             for i in start..<stop
 95             {
 96                 indegree[eles[i]] = nil
 97             }
 98             if start == stop
 99             {
100                 return false
101             }
102         }
103         return true
104     }
105 }
106 
107 /*扩展Int类，实现自增++、自减--运算符*/
108 extension Int{
109     //后缀++:先执行表达式后再自增
110     static postfix func ++(num:inout Int) -> Int {
111         //输入输出参数num
112         let temp = num
113         //num加1
114         num += 1
115         //返回加1前的数值
116         return temp
117     }
118 }