La solución más sencilla para este problema es el hallazgo sindical. El problema del número de islas puede ayudar a comprender cómo funciona la búsqueda de sindicatos.
La idea básica es que usamos un conjunto disjunto para rastrear cada componente. Siempre que se pueden conectar dos piedras, el número de islas disminuye en uno. El resultado final, el número de movimiento, es el número total de piedras, el número de islas.
Ejemplo 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5
Nota:
1 <= stones.length <= 1000
0 <= stones[i][j] < 10000
Solución Java 1 – Conjunto disjunto regular
class Solution { int[] root = new int[1000]; //value is index int result = 0; public int removeStones(int[][] stones) { result = stones.length; for(int i=0; i<stones.length; i++){ root[i]=i; } for(int i=0; i<stones.length; i++){ for(int j=i+1; j<stones.length; j++){ if(stones[i][0]==stones[j][0] || stones[i][1]==stones[j][1]){ union(i, j); } } } return stones.length-result; } public void union(int i, int j){ int ri = getRoot(i); int rj = getRoot(j); if(ri==rj){ return; } root[getRoot(i)]=getRoot(j); result--; } public int getRoot(int i){ while(i!=root[i]){ i=root[i]; } return i; } } |
La complejidad del tiempo es O (N ^ 2 * log (N)).
Solución Java 2: conjunto disjunto optimizado
class Solution { public int removeStones(int[][] stones) { DisjointSet ds = new DisjointSet(20000); for(int[] stone: stones){ ds.union(stone[0], stone[1]+10000); } HashSet<Integer> set = new HashSet<>(); for(int[] stone: stones){ set.add(ds.find(stone[0])); } return stones.length - set.size(); } } class DisjointSet{ int[] parent; public DisjointSet(int size){ parent = new int[size]; for(int i=0; i<size; i++){ parent[i] = i; } } public void union(int i, int j){ parent[find(i)] = find(j); } public int find(int i){ while(parent[i] != i){ i = parent[i]; } return i; } } |
La complejidad del tiempo es log (20000) * N = O (N)
