如何将稀疏矩阵划分为最少数量的连接组件,以便每个组件在整个组件中都有一个共同的行或列。我应该使用什么数据结构在最短的时间内完成这项任务。我认为这样做我必须最大化每个组件中的元素数量,因此在获取输入时我存储了每行和每列中的元素数量。我对列表进行排序,然后使用 max(min(行中的元素,列中的元素)) 对行或列进行排序,即
row 5-1 column 4-2
row 4-1 column 3-2
row 3-2 column 2-3
row 2-2 column 1-3
row 1-10
对于矩阵:
x
x
x x
x x
xxxxxxxxxx
(x代表非零位置)(这个矩阵的最终输出应该是4)
左下角是 1,1
然后我将首先删除第 1 列。然后我将不得不更新占用大量时间的剩余数组,并且为每行和每列存储列表也不可行,因为它使用大量内存。我只需要告诉最小分区数,而不是实际对矩阵进行分区。在给定的矩阵中,可以通过将 (row1,row2,row3,colum2-(1,2)) 作为分区来对其进行分区。
编辑:或者等效地,我们可以将其视为一组元素,该元素具有与它们相关联的两个数字,并且我们输出了最小数量的分区,使得每个分区都具有两个数字中的一个。