On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.
Now, a _move _consists of removing a stone that shares a column or row with another stone on the grid.
Input:
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Input:
stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Input:
stones = [[0,0]]
Output: 0
思路: 题目给出石头所在的坐标,只要两个石头在同一行或者同一列,则可以将其中一个石头拿走,问最多可以拿走多少个石头。其实这里拿走石头其实就相当于将一个石头归并到另一个石头中,这很典型的union-find的题目,union的规则也很简单,只要两个石头在同一行或者同一列即可。最后最多能拿走的石头的数量等于原来石头数量减去union中cluster的数目。
class Solution {
public int removeStones(int[][] stones) {
if (stones == null || stones.length == 0) {
return 0;
}
int n = stones.length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < stones.length - 1; i++) {
for (int j = i + 1; j < stones.length; j++) {
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
uf.union(i, j);
}
}
}
return n - uf.getCount();
}
class UnionFind {
int[] root;
int[] size;
int count;
public UnionFind (int n) {
root = new int[n];
size = new int[n];
count = n;
for (int i = 0; i < n; i++) {
root[i] = i;
size[i] = 1;
}
}
public int find(int node) {
while (node != root[node]) {
node = root[node];
}
return node;
}
public void union(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI == rootJ) return;
if (size[rootI] < size[rootJ]) {
root[rootI] = root[rootJ];
size[rootJ] += size[rootI];
}
else {
root[rootJ] = root[rootI];
size[rootI] += size[rootJ];
}
--count;
}
public int getCount() {
return count;
}
}
}
时间复杂度O(n^2 * logn), union-find的过程需要O(logn),遍历输入数组,检查它们的行或列是否相同需要O(n^2)时间, 空间复杂度O(n)