Skip to content

Latest commit

 

History

History
 
 

1632.Rank-Transform-of-a-Matrix

1632.Rank-Transform-of-a-Matrix

解法1:拓扑排序

拓扑排序是比较容易想到的方法。对于同一行(列)而言,如果把所有数字从小到大排列,那么较大的数字num[i]应该比它前面的数字num[i-1]的rank大,所以我们可以将构造一条从num[i-1]指向num[i]的路径。得到所有路径之后,我们就得到一张图。此时所有入度为0的这批点(即最外围的点)没有任何约束关系(意思是没有rank必须必它们小的其他点),故他们的rank就可以赋值为1. 将这批点剥离之后,剩下的所有入度为0的点,他们的rank可以赋值为2,以此类推。

但是有一种情况,就是同一行(列)中,如果有相同的数字,那么他们必须有相同的rank,因此在拓扑排序中需要把它们当做同一个点来处理。事实上,需要当做同一个点来处理的点可能有多个(而且会分布在不同的row或col里)。这就需要用union find来将这些点归并到同一个group里。同一个group的点在拓扑排序中只被处理一次,赋值相同的rank。

如果用拓扑排序来做,此题比较棘手的地方就是在于处理indegree。我们知道,拓扑排序的每个回合,我们剥离入度为0的点。在这里,我们需要将所有属于同一个group的点的入度要累加在一块儿计算。当整个group的入度为0的时候,我们才将其加入队列;当它弹出队列的时候,该group的所有点都赋予相同的rank。然后这些点的剥离会给各自next的点减少一个入度,但注意,这些入度的自减也必须都统计在整个group上。

解法2:贪心

我们将所有的点从到大排个序。全局最小点自然rank是1,并且对于该点所在行和列的其他数字,它们的rank必然要从2开始。

更general地,我们从小到大依次处理每个数字的时候,应该如何给它定rank呢?其实只要查看它所在的行、列各自已经赋值的rank。比如说,该行已经有其他数字被rank为3,该列已经有其他数字被rank为4,那么显然这个数字只能被rank为5.接下来,记得要把这个数字所在的行和列,都更新标记,因为它们已经赋值的rank变成了5. 根据这个规则我们就可以把所有数字都rank一遍。

同样,有一种情况需要处理,就是前面所说的,可能有一批数字必须有相同的rank。所以如果想要rank某个数,必须考察所有同属一个group的数(的行与列),才能确定这个rank。然后给它们赋值相同的rank,然后更新它们的行/列的已rank信息。