输入:单元格列表。每个单元格都有其顶部邻居的列表，其左侧邻居的列表。重新创建一个 excel 文件，其中包含与给定单元格列表的连通性相匹配的合并单元格。图表的整体形状和每个单元格都是矩形的，矩形内部没有空隙。总体规划:重建每个单元格的底部和右侧邻居列表。然后计算像元大小。
我有一种方法可以为每个单元格填充右邻居和下邻居列表，但这种方法很慢 O(n^2+)。我怎样才能让它更快？
我正在编写一个采用数组列表的方法，其中每个单元格都有一个名称和一个 listOfLeftNeighbors 以及一个空的 listOfRightNeighbors。然后它遍历列表并使用“如果你的 listOfLeftNeighbors 中有我，那么你将被添加到我的 listOfRightNeighbors”来填充 listOfRightNeighbors。然后它返回数组列表，其中为每个单元格填充了 listOfRightNeighbors。
private ArrayList<Cell> getRightNeighbors(ArrayList<Cell> set) {
for (int i = 0; i < set.size(); i++) { //for every cell in the list
List<String> myLeftNeighbor = set.get(i).getLeft(); //get a list of left neighbors
for (int j = 0; j < myLeftNeighbor.size(); j++) { //For each left neighbor of a given cell
String nameOfLeftNeighbor = myLeftNeighbor.get(j);
for (int k = i + 1; k < set.size(); k++) { //Check the list of cells and
String kName = set.get(k).getName();
if (0 == kName.compareTo(nameOfLeftNeighbor)) { //if name of k-th cell matches
set.get(k).addRight(set.get(i).getName()); //To list of right neighbors add the name of i-th cell
}
}
}
}
return set;
}
这至少是 O(n^2) 复杂度。有没有办法让这个方法更有效？
简而言之，初始数据由用户以excel格式提供。然后由拓扑处理器处理。每个单元格都有一个名称 getExcelName() + some_random_string .拓扑处理器多次拆分和合并单元格。当然，每次拓扑处理器拆分 A1 时，我都可以更新每个单元格的坐标(每个电子表格大约 100K 个单元格)，但这不是一个有效的算法。相反，拓扑处理器操纵单元的左邻域和上邻域列表。保持本地互动。拓扑操作完成后，应将数据转换为 excel 格式。
我认为项目的确切性质无关紧要。想象一组连接的管道。每条管道都连接到一些上游管道ArrayList<String> leftNeighbors和一套下游管道ArrayList<String> rightNeighbors .问题:给定一组带有 leftNeighbors 列表(上游)的管道，如何有效地填充 rightNeighbors 列表(下游)？
最佳答案
使用哈希，为每个单元格分配一个从 0 开始的数字。制作一个数组。用这些数字替换所有单元格名称。 O(n) 对于每个单元格 O(n) 执行此操作:
假设您使用单元格 8，它有一个邻居单元格 10。那么:listOfRightNeighblrs[10] = listOfRightNeighblrs[10] + ", 8"; O(1)(这是成功的关键)。
然后翻译回单元格名称，对于每个单元格 O(n) 从 listOfRightNeighblrs O(1) 填充它的右邻居。
到目前为止，它应该接近于 O(n*averageNumberOfNeighbors)。
关于java - 如何有效地查找 Java 中的链接单元格？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37548928/