使用联合查找，基本算法（无需担心内存）是：
- 为每个人创建一个集合
1
- 合并每对相邻的
1
s 的集合。顺序是什么都没关系，因此阅读顺序通常很好。 - 计算根集合的数量-每个岛都有一个。
简单，一点点地注意，就可以使用对矩阵的顺序访问和仅2行的内存来做到这一点：
- 初始化孤岛计数为0
- 阅读第一行，为每个行创建一个集合
1
，然后合并相邻列中的集合。 对于每个其他行：
- 读取行，为每个行创建一个集合
1
，然后将相邻列中的集合合并； - 合并新行中的集合与上一行中的相邻集合。始终将链接指向下方，这样您就永远不会在新行中找到与旧行中的父级链接的集合。
- 计算上一行中剩余的根集，然后将数字添加到孤岛计数中。这些将永远无法与其他任何东西合并。
- 丢弃上一行中的所有集合-您再也不需要它们了，因为您已经计算了它们，并且没有链接到它们。
- 最后，计算最后一行中的根集，并将其添加到岛数中。
- 读取行，为每个行创建一个集合
当然，关键是只要您在不同行中的链接集始终将链接指向下方。这不会损害算法的复杂性，而且，如果您使用自己的联合查找，则很容易实现。如果您使用的是库数据结构，则可以仅对每一行使用它，并自己跟踪不同行中的根集之间的链接。
因为这实际上是我最喜欢的算法之一，所以这里是Java的实现。这不是最易读的实现，因为它涉及一些低级技巧，但是效率极高且简短-
我会在性能非常重要的情况下写这种东西：
import java.util.Arrays;public class Islands{ private static final String[] matrix=new String[] { " ############# ### ", " # ##### ## ", " # ## ## # # ", " ### ## # # ", " # ######### ## ## ", " ## ## ", " ########## ", }; // find with path compression. // If sets[s] < 0 then it is a link to ~sets[s]. Otherwise it is size of set static int find(int[] sets, int s) { int parent = ~sets[s]; if (parent>=0) { int root = find(sets, parent); if (root != parent) { sets[s] = ~root; } return root; } return s; } // union-by-size // If sets[s] < 0 then it is a link to ~sets[s]. Otherwise it is size of set static boolean union(int[] sets, int x, int y) { x = find(sets,x); y = find(sets,y); if (x!=y) { if ((sets[x] < sets[y])) { sets[y] += sets[x]; sets[x] = ~y; } else { sets[x] += sets[y]; sets[y] = ~x; } return true; } return false; } // Count islands in matrix public static void main(String[] args) { // two rows of union-find sets. // top row is at even indexes, bottom row is at odd indexes. This arrangemnt is chosen just // to make resizing this array easier. // For each value x: // x==0 => no set. x>0 => root set of size x. x<0 => link to ~x int cols=4; int[] setrows= new int[cols*2]; int islandCount = 0; for (String s : matrix) { System.out.println(s); //Make sure our rows are big enough if (s.length() > cols) { cols=s.length(); if (setrows.length < cols*2) { int newlen = Math.max(cols,setrows.length)*2; setrows = Arrays.copyOf(setrows, newlen); } } //Create sets for land in bottom row, merging left for (int col=0; col<s.length(); ++col) { if (!Character.isWhitespace(s.charAt(col))) { int idx = col*2+1; setrows[idx]=1; //set of size 1 if (idx>=2 && setrows[idx-2]!=0) { union(setrows, idx, idx-2); } } } //merge up for (int col=0; col<cols; ++col) { int topidx = col*2; int botidx = topidx+1; if (setrows[topidx]!=0 && setrows[botidx]!=0) { int toproot=find(setrows,topidx); if ((toproot&1)!=0) { //top set is already linked down union(setrows, toproot, botidx); } else { //link top root down. It does not matter that we aren't counting its size, since //we will shortly throw it aaway setrows[toproot] = ~botidx; } } } //count root sets, discard top row, and move bottom row up while fixing links for (int col=0; col<cols; ++col) { int topidx = col * 2; int botidx = topidx + 1; if (setrows[topidx]>0) { ++islandCount; } int v = setrows[botidx]; setrows[topidx] = (v>=0 ? v : v|1); //fix up link if necessary setrows[botidx] = 0; } } //count remaining root sets in top row for (int col=0; col<cols; ++col) { if (setrows[col*2]>0) { ++islandCount; } } System.out.println("nThere are "+islandCount+" islands there"); }}
