1

我需要将所有数字（在一个集群中可以是具有相同值的数字，例如只有 5）聚集在不同于传递的矩阵中并返回字典，如

    {number1:[[(3,4),(4,5)],[]..], number2:...}#I am using Python

我可以遍历行和列，当我发现与传递的数字 x 不同的数字时，我开始填充并创建集群并记住访问过的位置，以避免重复相同的集群，并且它可以工作。我想知道有没有人有更好的想法，更快？

例如（我想聚集所有不同于 1 的数字） 传递值 1

2  1  1  2
2  1  2  2 
1  1  3  3

我会得到 { 2:[(0,0),(1,0)],[(0,3),(1,2)(1,3)], 3:[(2,2),(2 ,3)]}

4

2 回答 2

1

让我们将单元格值分类为target value和replacement value(s)，其中带有的单元格target value是您要修改的单元格。你想用replacement value(s). 在您的示例中，这些值恰好分别为 1 和 (2,3)。

Flood-fill 的一种常见应用是将单元格更改为带有replacement value(s)的单元格target value，例如油漆应用中的桶填充工具。如果这是您的用例，您可以在每次访问单元格时简单地更改单元格值，从而无需记住您之前是否访问过它。我假设这不是你的用例。

方法#1：使用字典

我会使用带有访问单元格的（行，列）作为键的字典。由于您想查看是否访问过 (row, col)，因此可以在 O(1) 时间复杂度内完成。您的方法需要首先转到特定replacement value键，然后遍历列表以查找 (current row, current col) 是否存在于其中。它的时间复杂度与 O(k) 成正比，其中 k 是列表中元素的数量。在最坏的情况下，它将是 O(RxC)，其中 RxC 是矩阵的维度。

方法#2：使用布尔矩阵

另一种简单的方法是使用与单元格值矩阵具有相同维度的 bool 类型的矩阵。每次访问一个单元格时，将其标记为 True。您可以在 O(1) 中检查一个单元格是否已被访问过。

在最坏的情况下，上述两种数据结构都将具有 O(RxC) 的空间复杂度。我假设这很好，因为您已经有一个相同顺序的单元格值矩阵。

于 2013-01-21T16:39:36.143 回答
1

您是否考虑过使用numpy.where()？如果您可以将数据放入数组中，则可以简单地使用：

 import numpy as np
 data=np.array(<some data>)
 np.where(data!=2)

抓取不等于二的元素的索引。就此而言，numpy 数组的工作与直接比较这样

 data > 5

将返回一个布尔数组，其中比较为真，并且：

 data[data > 5]

将返回比较为真的值，这样您甚至可能不需要 numpy.where()。

于 2013-01-21T16:39:50.763 回答