輸入:單元格列表。每個單元格都有一個頂部鄰居列表,它的左邊鄰居列表。使用合併的單元重新創建一個excel文件,該文件將與給定的單元格列表的連接相匹配。圖表和每個單元格的整體形狀都是矩形,並且矩形內沒有空隙。整體計劃:重建每個單元格的底部和右側鄰居列表。然後計算單元大小。如何在Java中高效查找鏈接的單元格?
我有一個方法可以爲每個單元填充右邊和底部的鄰居列表,但是這種方法很慢O(n^2 +)。我怎樣才能讓它更快?
我正在寫一個採用arraylist的方法,其中每個單元格都有一個名稱,一個listOfLeftNeighbors和一個空listOfRightNeighbors。然後,它遍歷列表,並使用「,如果你有我在你listOfLeftNeighbors,那麼你加入到我的listOfRightNeighbors充滿listOfRightNeighbors,然後返回與填充每個單元格listOfRightNeighbors ArrayList中。
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
。拓撲處理器多次拆分和合並單元格。當然,我可以更新每個單元格的te座標(每個電子表格有大約100K個單元格),每次拓撲處理器將A1分開時,但這不是一個有效的算法。相反,拓撲處理器操縱單元的左邊和頂部鄰居列表。保持互動本地。一旦拓撲操作完成,數據應該轉換爲excel格式。
我不認爲項目的確切性質是相關的。想象一組連接的管道。每個管道連接到一些上游管道ArrayList<String> leftNeighbors
和一組下游管道ArrayList<String> rightNeighbors
。問題:給定一組具有左鄰居(上游)的管道,如何有效地填充右鄰居(下游)的列表?
它看起來像你正在做某種樹,並且你有會員資格測試。您應該可能描述您正在嘗試構建的數據結構,以及爲什麼它只是一個由不可思議的過程操作的幾個非常名稱的列表。 – pvg
我已經添加了解釋。 – Steve
看一下Cell類,也許解釋一下爲什麼這些單元格代表他們會幫助我們很多。具體來說,爲什麼應該表示電子表格單元格的是互連對象列表的形式,而不是二維列表或數組內的元素,這是一個更類似於電子表格的數據結構(並且很可能是如何電子表格甚至可以在大多數spreasheet程序中實現)。 –